소심야채

https://www.acmicpc.net/problem/2365 2365번: 숫자판 만들기 입력의 첫째 줄에는 행(열)의 크기 N이 주어진다(1 ≤ N ≤ 50). 둘째 줄에는 N개의 정수가 주어진다. 주어지는 정수는 1행부터 N행까지의 합을 차례대로 나타낸다. 셋째 줄에는 N개의 정수가 주어 www.acmicpc.net [문제설명] - N*N 숫자판(숫자판의 수들은 주어지지 않음)의 N개의 행과 N개의 열의 합이 주어진다. - 숫자판의 배정된 수들은 0이상의 정수이다. - 조건을 만족하는 배정된 수 중에서 최댓값을 최소로 하는 숫자판을 찾아야한다. [문제풀이] - 지문에서 주어지는 입력을 시각화하면 아래와 같습니다. c* = max(a, b, c, d)일때 c*의 값을 최소로하는 숫자판의 형태를 찾아..

https://www.acmicpc.net/problem/27469 27469번: 퀸 움직이기 숙제를 하지 않고 체스와 조합론에 빠져있던 은재가 생활관에 체스판을 하나 들고 왔다. 이 체스판은 특이해서 $8 \times 8$ 형태의 기본적인 판 뿐만 아니라 $17 \times 19$ 크기나 심지어 $1 \times 100$ www.acmicpc.net [문제설명] - N행 M열로 구성된 체스판의 정보와 퀸의 시작 좌표와 도착 좌표가 주어진다. - 체스판 각 칸에는 장애물(#)이 있거나 빈 칸(.)으로 구성되어 있다. - 퀸은 8방향(상하좌우, 대각선)으로 장애물이 없을경우 거리 제한없이 이동가능하다. - 두 번 연속으로 같은 방향으로 움직일 수 없다. - 시작 좌표로 부터 K번 이동하였을 때 도착 좌표로..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net [문제설명] - n개의 재료를 각각 사용 또는 사용안해도 된다. - 각 재료는 신맛 S와 쓴맛 B를 가지고 있다. - 재료 선택을 마친 후 선택된 재료의 신맛을 곱하고 쓴맛은 더했을 때 두 값의 가장 작은 차이를 출력해야 한다. - 재료는 적어도 하나 사용해야 한다. [문제풀이] - n개의 재료를 사용하거나 사용안해도 무방하니 재료선택의 총 경우의 수는 2^n입니다. - n이..

https://www.acmicpc.net/problem/26518 26518번: 수열의 극한값 첫 번째 줄에 정수 $b$, $c$, $a_1$, $a_2$가 공백으로 구분되어 주어진다. $(1 \leq b, c, a_1, a_2 \leq 10^9)$ www.acmicpc.net 문제풀이 $$a_i = b*a_{i-1} + c*a_{i-2} (i \geq 3)$$ 수열 a가 주어졌을때 $$\lim_{n \to inf}\frac{a_n}{a_{n-1}}$$ 값을 구하는 문제로써 문제에서 항상 이 값이 수렴되어짐이 보장되어 있다. 문제에서 주어지는 정수범위로 인해 순차적으로 수열값(a_n)을 구하면서 극한 값을 접근하는 시도는 long long int를 사용하더라도 오버플로우가 발생한다. 따라서 적절하게 식..

#include #include #include #include using namespace std; typedef long long LL; const int MAX_N = 100010; int sqrtN; struct Query { int idx, s, e; bool operator < (Query &x) { if (s / sqrtN != x.s / sqrtN) return s / sqrtN < x.s / sqrtN; return e < x.e; } }; vector query; int arr[MAX_N], cnt[MAX_N*10]; LL ret = 0, ans[MAX_N]; void add(int x) { ret += (LL)(2 * ++cnt[x] - 1)*x; } void sub(int x) { ..

전형적인 knapsack problem 문제이다. #include #include #include #include using namespace std; typedef pair pii; const int MAX_N = 100; const int MAX_T = 10010; int cache[MAX_N][MAX_T]; int n, t; pii test[MAX_N]; //{studyTime, score} int solve(int idx, int time) // idx단원 이후에 얻을수있는 최대점수 { if (idx == n) return 0; int& ret = cache[idx][time]; if (ret != -1) return ret; ret = solve(idx + 1, time); // idx단원 공부..

#include #include #include using namespace std; const int MAX_N = 100 + 5; const int MAX_W = 100100; int main() { int N, K; int W[100100]; int dp[MAX_N][MAX_W]; // dp[i][j] = [0...i]번 배낭을 사용하여 총합무게 j일때 얻을 수 있는 가치의 최댓값 int weight[MAX_N], value[MAX_N]; scanf("%d %d", &N, &K); for (int i = 1; i

https://www.acmicpc.net/problem/10165 [문제조건] 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000), 버스 노선의 수 M(2 ≤ M ≤ 500,000) 각 버스의 노선 [a,b] 단, 0 ≤ a,b ≤ N-1이고 a ≠ b [문제풀이] 조건 a ≠ b 로 인하여 각 버스의 노선 [a,b]를 두 분류로 나눌수가 있다. \[\displaystyle \begin{cases}ab & passZeroZone\end{cases}\] ZeroZone == [n-1,0] 그룹 A의 특징으로는 (n-1)번과 0번사이 도로를 지나가지 않으며, 그룹 B의 특징으로는 (n-1)번과 0번사이 도로를 무조건 지나간다. 따라서 그룹A는 그룹 B를 포함할수 없는점을 알수가 있으며, 그룹 ..