다이나믹 프로그래밍

문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 격자상에서 각 칸에 도달할 수 있는 경로의 경우의 수는 다음과 같다. 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 0번 행과 0번 열은 모두 한가지의 방법만 존재한다. (x, y) 칸에 도달할 수 있는 경로의 수는 (x - 1, y) 칸과 (x, y - 1) 칸에 올 수 있는 경우의 수의 합이다. 중간 경로 K를 지나면서 마지막 칸에 도달하는 경우의 수는 (1번 칸에서..

문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 다리는 서로 겹쳐질 수 없으므로, 동쪽의 사이트 M개 중에서 N개의 사이트를 선택하는 경우의 수이다. int Combination(int n, int r) { if (n == r || r == 0) { return 1; } else { return Combination(n - 1, r - 1) + Combination(n - 1, r); } } 단순히 위의 함수로만 구하면 시간 초과가 발생한다. 다이나믹 프로그래밍을..

문제 풀이 다이나믹 프로그래밍 문제이다. https://kantatatam.tistory.com/155 [백준][C++] 27210: 신을 모시는 사당 문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 kantatatam.tistory.com 위의 문제와 유사하다. 선택한 수의 배열의 총합을 current로 생각한다. 배열을 탐색하면서 current에 현재 요소의 값(nums[i])을 더한다. current가 현재 요소의 값보다 작다면, 기존의 배열을 버리고, 현재 요소를 첫 요소로 하는 새로운 배열을 생성한다. current의 최댓값이 답이다. 코드 #in..

문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 과반수인 배열. (left) 첫 요소가 오른쪽인 배열. 오른쪽이 과반수인 배열. (right) 전체 배열을 탐색하면서 돌상이 왼쪽인 경우에는, left 배열의 깨달음의 양이 1 증가하면서, right 배열의 깨달음의 양이 1 감소한다. 돌상이 오른쪽인 경우에는, left 배열의 깨달음의 양이 1 감소하면서, right 배열의 깨달음의 양이 1 증가한다. 현재 배열의 깨달음의 양이 0미만이라면 해당 배열을 버린다. 현재 배열 2개의 깨달음의 양의 최대값이 답이다. 코드 #include #include using..

문제 풀이 다이나믹 프로그래밍 문제다. 모든 단계에서 모든 발의 위치의 최솟값을 cache로 담는다. 현재 단계를 검사할 때, 이전 단계의 cache를 사용한다. 이전 단계에서 발의 위치가 존재할 수 없는 것은 제외한다. 이전 단계에서 왼발/오른발을 현재 옮겨야 하는 위치로 옮겼을 때의 비용의 최솟값을 cache로담는다. 왼발을 움직이는 경우 cache[현재 단계][현재 옮겨야 하는 위치][오른발] = min( cache[현재 단계][현재 옮겨야 하는 위치][오른발], cache[이전 단계][이전 왼발의 위치][오른발] + (이전 왼발발에서 현재 옮겨야 하는 위치로의 비용) ) 오른발을 움직이는 경우 cache[현재 단계][왼발][현재 옮겨야 하는 위치] = min( cache[현재 단계][왼발][현재 ..

문제 풀이 다이나믹 프로그래밍을 사용한다. N번 집을 칠할 때, 1번 집의 색의 영향을 받는다. 1번 집을 R로 칠한 경우, G로 칠한 경우, B로 칠한 경우 세 가지를 모두 검사해야 한다. 1번 집을 칠한 색이외의 cache에는 충분히 큰 값을 두어 2번 집을 칠할 때 선택되지 않도록 해야한다. i번 집을 j색으로 칠했을 때의 최솟값은 i번 집을 j색으로 칠한 비용과 i - 1번 집을 j 이외의 색으로 칠한 비용의 합의 최솟값이다. N번 집은 1번 집을 칠했을 때의 색으론 칠할 수 없으니 그 경우는 제외해야 한다. 코드 #include #include #include using namespace std; int house[1001][3]; int cache[1001][3]; int main() { io..

문제 풀이 다이나믹 프로그래밍 문제로 S와 E가 입력될 때마다 처음부터 검사하면 시간초과이다. S와 E가 같다면 무조건 팰린드롬이다. S와 E가 1차이라면 num[S]와 num[E]만 검사하면 된다. S와 E에서부터 시작해서 num[S]와 num[E]가 같으면서 사이의 수열이 팰린드롬이라면 그 수열은 팰린드롬이다. 여기서 S와 E의 값을 각각 1늘리고 1줄이는 방식으로 검사하면서 num[S]와 num[E]가 같지않다면 그 수열은 팰린드롬이 아니다. '\n' 을 사용해야 한다. endl을 사용할 경우 시간초과가 발생한다. 코드 #include using namespace std; bool cache[2001][2001]; int num[2001]; int main() { ios_base::sync_with..

문제 풀이 다이나믹 프로그래밍 문제로 string 2차원 배열을 사용해서 cache와 같이 추가하면 시간초과가 발생한다. cache를 갱신시키면서 cache의 경로를 따로 저장하거나, 결과값에서부터 역추적하여 정답에 접근해야 한다. 코드 경로를 저장하는 방법 #include #include #include using namespace std; int cache[1001][1001]; // 경로를 저장하는 배열 pair path[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); string a; string b; cin >> a >> b; a = '0' + a; b = '0' + b; for (int ..

문제 풀이 바이토닉 부분 수열의 가운데 값을 찾는 것으로 생각하는게 쉽다. 수열의 앞에서부터 탐색하여 증가하는 값을 cache로 두고, 마찬가지로 뒤에서 부터 탐색하여 증가하는 값을 cache_reverse로 둔다. cache와 cache_reverse의 합이 최대가 되는 인덱스를 찾는다. 코드 #include using namespace std; int main() { int N; int A[1001]; cin >> N; for (int i = 1; i > A[i]; } if (N == 1) { cout = i; --j) { if (A[i] > A[j]) { maxi = max(maxi, cache_reverse[j]); } } cache_reverse[i] = maxi + 1; } // 가장 긴 바이..

문제 풀이 DP와 그래프 탐색으로 풀 수 있다. 코드 그래프 탐색 #include #include #define VER 0 #define HOR 1 #define DIA 2 using namespace std; typedef struct { int x; int y; int dir; }type; // 파이프의 방향에 따른 이동 위치 vector move_x = { {0, -1, 1}, {-1, 1, 1}, {0, 1, 1} }; vector move_y = { {1, -1, 1}, {-1, 0, 1}, {1, 0, 1} }; // 파이프의 방향과 이동 위치에 따른 검사 위치 int check_x[3] = { 1, 1, 0 }; int check_y[3] = { 0 ,1, 1 }; //vector check..