재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍을 사용하여 최적해를 구한 뒤, 최적해로 다다르는 경로의 개수를 세는 문제이다. 이 문제에 대해 경로의 개수를 세는 부분이 어려웠는데, 앞서 구했던 dp 배열을 통해 구할 수 있다는 힌트를 얻었다. 바로 아래와 아래 오른쪽 둘 중 dp 배열의 값이 큰 쪽으로 재귀를 호출하며, 만약 같을 경우에는 둘 다 최적해 경로일 가능성이 있으므로 둘 다 호출한 뒤 더해주면 된다. 이미 dp 배열을 사용하는데 왜 countDP가 따로 필요할 까 의문이 들었는데, 만약 삼각형의 모든 수가 같다면 재귀 호출을 매우 많이 하게 된다. 이를 방지하기 위해서는 coundDP가 또 필요하게 된다. #include #include using namespace std; #define MAX 100 int..

다이나믹 프로그래밍의 대표적인 문제이다. i번째 2 x 1 칸을 어떻게 채울지를 생각하면 쉽게 풀 수 있다. 2 x 1 블록 하나로 세울 경우 i - 1번까지를 채운 경우의 수와 일치하게 되고, 1 x 2 블록 두개를 세운 경우 i - 2번까지를 채운 경우의 수와 일치하게 된다. 따라서 dp[i] = dp[i - 1] + dp[i - 2] 이고, 이를 계산하면 쉽게 풀 수 있다. #include using namespace std; #define MAX 100 #define MOD 1000000007 int dp[MAX + 1]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int C; cin >> C; dp[1] = 1; dp..

이 문제는 다이나믹 프로그래밍을 이용한 문제이다. 문자열을 3 ~ 5글자씩 끊어서 읽고, 각 읽는 난이도를 모두 더했을 때의 최솟값을 리턴하는 문제이다. 문자열 S를 3글자 끊고 남은 나머지 문자열에 대한 재귀 연산을 수행하는 방식으로 구현했다. 이 때 나머지 문자열을 구하는 문제는 앞의 문제에 의존적이지 않으므로 다이나믹 프로그래밍을 사용할 수 있고, 시작 위치에 대한 값을 dp 배열에 저장함으로써 빠르게 구할 수 있었다. #include #include using namespace std; int toNumber(char c) { return c - '0'; } int absolute(int num) { if (num < 0) { return -num; } return num; } bool diff1..

이 문제는 다이나믹 프로그래밍을 풀 수 있는 문제이다. 수열 A에 대해 dp[i]를 A[..i] 까지의 LIS로 정의하면, 이중 for문만으로 문제를 해결할 수 있다. 수열의 최대 길이가 500이므로, 시간 안에 충분히 풀 수 있다. #include #include using namespace std; #define MAX 500 int arr[MAX]; // dp[i] : arr[..i] 까지의 LIS int dp[MAX]; void init(int N) { for (int i = 0; i > C; for (int..

이 문제는 다이나믹 프로그래밍으로 풀 수 있는 문제이다. 완전 탐색으로는 2^100 이므로 시간 초과가 나지만, 메모이제이션을 통해 O(n^2) 으로 만들 수 있다. n의 최댓값이 100이므로 충분히 시간 안에 풀 수 있다. #include #include using namespace std; #define MAX 100 int n; int triangle[MAX + 1][MAX + 1]; int dp[MAX + 1][MAX + 1]; int solve(int depth, int index) { if (depth == n + 1) { return 0; } if (dp[depth][index] != -1) { return dp[depth][index]; } // straight int result = 0;..

이 문제는 다이나믹 프로그래밍으로 간단하게 해결할 수 있다. 이 문제에서 격자의 최대 크기는 100 x 100 이고, 각 칸에서 오른쪽이나 아래를 선택해야 한다. 따라서 완전 탐색으로는 O(2^10000) 이므로 절대 시간 안에 풀 수 없다. 그러나 다이나믹 프로그래밍을 사용하면 이미 있는 (y, x) 결과에 대해서 바로 리턴하므로 dp 배열을 다 채우는 시간만큼만 연산을 수행하게 된다. 따라서 O(n^2) 이 되고, 시간 안에 충분히 풀 수 있게 된다. #include #include using namespace std; #define MAX 100 int matrix[MAX][MAX]; int n; int dp[MAX][MAX]; void init() { for (int y = 0; y < n; y+..

이 문제는 완전 탐색에 메모이제이션을 더한 다이나믹 프로그래밍으로 풀 수 있다. 완전 탐색으로 풀게 되면 시간 초과가 나게 되는데, 이를 메모이제이션으로 결괏값을 저장해주고, 저장되었다면 바로 리턴하도록 만들면 시간 안에 풀 수 있다. #include #include #include using namespace std; #define BOARD_SIZE 5 char board[BOARD_SIZE][BOARD_SIZE]; int dy[] = { -1, 1, 0, 0, -1, -1, 1, 1 }; int dx[] = { 0, 0, -1, 1, -1, 1, -1, 1 }; int dp[BOARD_SIZE][BOARD_SIZE][11]; void init() { for (int y = 0; y < BOARD_S..

이 문제의 경우 분할 정복을 이용해서 풀었다. 압축된 결과를 보여주고, 이를 상하로 뒤집은 결과를 리턴해야 하는 문제였다. x일 때는 사분면으로 나눠지게 되는데, 왼위, 오위, 왼아, 오아 네가지로 생각했을 때 상하로 뒤집게 된다면 왼아, 오아, 왼위, 오위 순서로 탐색하면 뒤집힌 결과가 나오게 된다. 이를 활용하면 쉽게 풀 수 있는 문제이다. #include #include using namespace std; int index; string parse(string& input) { if (input[index] == 'x') { string present = ""; present += input[index++]; string leftUp = parse(input); string rightUp = pa..