이전 강의에선 쉽게 해결이 가능한 1차원 다이나믹 문제들이었다면 이번엔 약간 생각이 필요한 문제들이다. 이번엔 문제의 변수가 추가된 2차원 다이나믹 문제들을 풀어보자
<11052번 / 카드 구매하기>
카드 N개를 구매해야 한다. 이 때 카드팩은 총 N가지 종류가 존재한다. i번째 카드팩에는 i개의 카드가 들어있고, 가격은 P[i]원이다. 이 때 카드 N개를 구매하는 비용의 최댓값을 구하는 문제이다. 그러면 점화식 D[N]을 우선 카드 N개를 구매하는 비용의 최댓값으로 두자. 이도 전에 푼 문제처럼 마지막 카드팩에 집중하여 작은 문제로 쪼갠다. 근데 마지막 카드팩에 카드가 몇 개있는지 알 수 없다. 그래서 마지막 카드팩에 카드가 i개 있다고 가정한다. 그러면 그 전에 N-i개의 카드를 구해야 한다. 그래서 점화식 D[N] = max(D[N-i] + P[i])가 된다.(D[N-i] -> N-i개의 카드를 구매하는 비용의 최댓값 / P[i] -> i번째 카드팩의 비용 / 이 둘의 합의 최댓값이 D[N]이 된다)
그럼 이 문제의 시간복잡도를 구해보자. 문제의 시간 복잡도는 "전체 문제의 개수 * 하나의 문제를 푸는데 걸리는 시간의 최댓값"이다. 여기서 전체 문제의 갯수는 총 N개가 된다.(D[N]이니까) 하나의 문제를 푸는데 걸리는 시간은 i의 범위에 따라 달라지게 된다. 마지막 카드팩의 카드 개수인 i의 범위는 1<=i<=N이다. 따라서 이의 시간복잡도는 O(N)이 된다. 그러면 둘을 곱하면 최종 시간복잡도는 O(N^2)이 된다.
그럼 코드로 직접 구현해보자!
값의 최댓값을 저장하는 배열 d[MAX]와 카드팩의 가격을 저장하는 배열 p[1000]이 있다. 이 때 p배열에 입력할 때 i번째 카드의 가격이 p[i]이기 때문에 p[0]=0을 먼저 저장하고 d[0]=0도 먼저 예외처리를 해준다. 그리고 i 반복문은 1부터 n까지 반복하고 j 반복문은 1부터 i까지 돌려주면서 d[i]와 d[i-j] + p[j]의 최댓값을 d[i]에 저장해준다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 10000000 int p[1000]; int d[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; p[0] = 0; for (int i = 1; i <= n; i++) { cin >> p[i]; } d[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { d[i] = max(d[i], d[i - j] + p[j]); } } cout << d[n] << '\n'; return 0; } |
cs |
<16194번 / 카드 구매하기 2>
이 문제는 위문제와 달리 최솟값을 구하는것이다. 얼핏보면 전 문제에서 max를 min으로만 바꾸면 될 것 같지만 실제로는 그렇지 않다! 물론 점화식은 D[i] = min(D[i], P[j]+D[i-j])가 맞지만 여기서는 배열의 초기값을 조심해줘야 한다. min으로 할 때 배열의 초기값이 0이라면 어떤 값이 들어와도 0이 작아서 계속 0만 저장되기 때문에 배열의 초기값을 설정한 후 반복문을 통해 D[i]를 구해줘야 한다.
두 개의 초기화 방법으로 코드를 구현해보자.
- 변수의 제한 범위를 사용하여 초기화
초기화하고 이전 코드에서 max를 min으로만 바꿔주었다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 10000000 int p[1000]; int d[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; p[0] = 0; for (int i = 1; i <= n; i++) { cin >> p[i]; } d[0] = 0; for (int i = 1; i <= n; i++) { d[i] = 10000000; //1000 * 10000 } for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { d[i] = min(d[i], d[i - j] + p[j]); } } cout << d[n] << '\n'; return 0; } |
cs |
- 배열을 -1로 초기화
여기서는 min을 사용하지 않고 if문으로 처리하였다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 10000000 int p[1000]; int d[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; p[0] = 0; for (int i = 1; i <= n; i++) { cin >> p[i]; } d[0] = 0; for (int i = 1; i <= n; i++) { d[i] = -1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { if (d[i] == -1 || d[i] > d[i - j] + p[j]) { d[i] = d[i - j] + p[j]; } } } cout << d[n] << '\n'; return 0; } |
cs |
<15990번 / 1, 2, 3 더하기 5>
1, 2, 3 더하기 문제에서 같은 수를 연속해서 사용하면 안된다는 조건이 추가된 문제이다. 그래서 이전 점화식에서 연속 조건을 포함하기 위해 약간의 변경이 필요하다. 연속 조건을 만족하려면 바로 이전에 사용한 숫자를 제외한 숫자를 사용하면 된다. 그러기 위해 마지막에 사용한 수를 j라고 하여 기억하도록 한다. 그러면 점화식은 다음과 같다.
D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, j는 마지막에 사용한 수이다.
이 문제또한 초기화를 조심해야 한다. D[0]을 1로 그냥 초기화해버리면 이차원 배열에서 중복이 발생하여 D[i][1~3]에서 예외처리를 해줘야 한다.
코드구현해보자. 아니 또 int가 일냈다..... 진짜 짜증나네 아니 코드상에 틀린게 없어서 뭐지 했더니 배열형을 int에서 long long으로 바꾸니까 됐어....아 짜증나 진자ㅠㅠㅠㅠ 그리고 초기화 부분에서 엄청 해멨다. 연속이란 조건을 까먹고 초기화하니까 계속 틀려서 뭐지 했는데....아 암튼 험난했다. 초기화만 조심하면 점화식은 설명대로 하면 됐다. 최종 출력은 d[n][1] + d[n][2] + d[n][3] 이런식으로 하면 됐다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 100001 long long d[MAX][4]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t;
d[0][1] = 0; d[0][2] = 0; d[0][3] = 0;
d[1][1] = 1; d[1][2] = 0; d[1][3] = 0;
d[2][1] = 0; d[2][2] = 1; d[2][3] = 0;
d[3][1] = 1; d[3][2] = 1; d[3][3] = 1;
for (int i = 4; i < MAX; i++) { d[i][1] = (d[i - 1][2] + d[i - 1][3]) % 1000000009; d[i][2] = (d[i - 2][1] + d[i - 2][3]) % 1000000009; d[i][3] = (d[i - 3][2] + d[i - 3][1]) % 1000000009; } while (t--) { int n; cin >> n; cout << (d[n][1] + d[n][2] + d[n][3]) % 1000000009 << '\n'; } return 0; } |
cs |
<10844번 / 쉬운 계단 수>
인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다. 이 문제는 길이가 n인 계단 수의 개수를 구하는 문제다. 이 문제도 연속 조건처럼 마지막에 사용한 숫자를 기억하여 푼다. 점화식을 세우면 아래와 같다.
>D[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수
만약 n번째 수가 a였다면 n-1번째에는 a-1, a+1만 올 수 있다. 그러면 D[n-1][a-1]+D[n-1][a+1]이 된다.
>D[i][j] = D[i-1][j-1] + D[i-1][j+1]
여기서 i가 0이면 음수, 9면 10이되므로 0과 9는 예외가 발생하므로 예외처리를 해주어야 한다.
이제 코드 구현하자자자자자~~~
조건문으로 0이랑 9 예외처리하고 반복문으로 구현하였따. 또 문제생길까봐 long long으로 해버림ㅎㅎ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <algorithm> using namespace std; long long d[101][10]; #define mod 1000000000 int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= 9; i++) d[1][i] = 1; for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { d[i][j] = 0; if (j - 1 >= 0) d[i][j] += d[i - 1][j - 1]; if (j + 1 <= 9) d[i][j] += d[i - 1][j + 1]; d[i][j] %= mod; } } long long res = 0; for (int j = 0; j <= 9; j++) { res += d[n][j]; } cout << res % mod << '\n'; return 0; } |
cs |
<2193번 / 이친수>
이친수는 아래의 조건을 만족하는 이진수를 말한다.
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
이 문제는 n자리 이친수의 개수를 구하는 문제이다. 이 연속조건과 비슷하게 점화식을 세우면 된다. 그러면 아래와 같다.
>D[i][j] = i자리 이친수의 개수 중에서 j로 끝나는 것의 개수 (j = 0, 1)
위의 점화식에서 j=0이면 점화식은 D[i-1][0] + D[i-1][1]로 나타낼 수 있다. j=1이라면 1은 연속할 수 없기 떄문에
D[i-1][0]이다. 최종 점화식은 이 두 식을 더해주면 된다. 이 때 D[1][0]과 D[1][1]의 초기값은 0과 1로 해준다. (생각해보면 당연한거임)
그럼 이차원 다이나믹으로 코드를 구현해보자
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <algorithm> using namespace std; long long d[91][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; d[1][0] = 0; d[1][1] = 1; for (int i = 2; i <= n; i++) { d[i][0] = d[i - 1][0] + d[i - 1][1]; d[i][1] = d[i - 1][0]; } cout << d[n][0] + d[n][1] << '\n'; return 0; } |
cs |
또한 이 문제는 1차원 다이나믹 문제로 풀 수도 있다. 여기서 문제의 차원은 점화식에 들어있는 변수의 개수라고 생각하면 쉽다. D[n]을 n자리 이친수라고 하면 이도 마지막수로 나눠서 풀면 된다. 마지막수가 0이면 n-1번째에는 1또는 0이 올 수 있으므로 D[n-1]이다. 하지만 1이면 n-1번쨰에는 0이 올수밖에 없고 n-2번째부터 0또는 1이 올 수 있기 때문에 D[n-2]가 된다. 따라서 D[n] = D[n-1] + D[n-2]이다.
이로 코드를 구현해보면 다음과 같다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <algorithm> using namespace std; long long d[91]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; d[1] = 1; d[2] = 1; for (int i = 3; i <= n; i++) { d[i] = d[i - 1] + d[i - 2]; } cout << d[n] << '\n'; return 0; } |
cs |
이친수까지 끝!
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 4강 다이나믹 프로그래밍 1 - 연습 (0) | 2020.08.25 |
|---|---|
| 4강 다이나믹 프로그래밍 1 - 합분해까지 (0) | 2020.08.24 |
| 4강 다이나믹 프로그래밍 1 - 1, 2, 3 더하기까지 (0) | 2020.08.22 |
| 4강 다이나믹 프로그래밍 1 - 다이나믹 프로그래밍 소개 (0) | 2020.08.21 |
| 3강 수학 1 - 참고 (0) | 2020.08.20 |
댓글