백준 Bottom-UP DP 문제들 2
알고리즘 기초 문제 중 DP 기본 문제(400)
이 중 bottom-up 방식의 2차원 DP 문제들
1. 1,2,3 더하기5
정수 N을 1,2,3의 합으로 나타내는 방법의 개수를 구하는 문제.
단, 같은 수를 두번 이상 연속해서 사용하면 안된다
1,2,3 더하기 문제의 업그레이드 버전
예시
일단 해당 수를 만들 수 있는 모든 경우의 수를 확인해보면 다음과 같다
1
2
3
4
1 = 1
2 = 1+1, 2
3 = 1+1+1, 1+2, 2+1, 3
4 = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+2, 2+1+1, 3+1
다음과 같이 만들 수 있다
점화식
dp[i][j]를 i를 만드는데, j로 끝나는 방법의 개수라고 하면
1
2
3
4
5
6
7
8
9
dp[1][1] = 1; // 1을 만드는데, 1로 끝나는 방법 : 1개 (1)
dp[2][1] = 0; // 2를 만드는데, 1로 끝나는 방법 : 0개 (1+1은 불가능)
dp[2][2] = 1; // 2를 만드는데, 2로 끝나는 방법 : 1개 (2)
dp[3][1] = 1; // 3을 만드는데, 1로 끝나는 방법 : 1개 (1+1+1은 불가능, 2+1 가능)
dp[3][2] = 1; // 3을 만드는데, 2로 끝나는 방법 : 1개 (1+2)
dp[3][3] = 1; // 3을 만드는데, 3로 끝나는 방법 : 1개 (3)
...
로 볼 수 있다.
dp[i][1] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3]인데, 같은 수를 두번 이상 연속해서 사용하면 안되므로
dp[i-1][1]를 제외한 dp[i][1] = dp[i-1][2] + dp[i-1][3] 로 나타낼 수 있다
마찬가지로 dp[i][2] = dp[i-2][1] + dp[i-2][3], dp[i][3] = dp[i-3][1] + dp[i-3][2] 로 정리할 수 있다
dp[N][1, 2, 3]을 각각 구해서 더해주면 된다
- 주의! dp[i]를 더하는 과정에서 INT형을 초과할 수 있으므로,
int보다 더 큰 자료형을 사용할것이 아니라면, 연산 시 MOD로 나눠주는 작업을 수행해주어야함
소스코드
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
43
44
45
46
#include <iostream>
#define MOD 1000000009
using namespace std;
int T, N;
int dp[100001][4]; // N을 만드는데, 1, 2, 3으로 끝나는 방법
// MOD로 나눠주기때문에 overflow는 발생하지 않음
void init() {
/*
중복을 포함해서 만들 수 있는 경우의 수
1 = 1
2 = 1+1, 2
3 = 1+1+1, 1+2, 2+1, 3
4 = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+2, 2+1+1, 3+1
*/
dp[1][1] = 1; // 1을 만드는데, 1로 끝나는 방법 : 1개 (1)
dp[2][1] = 0; // 2를 만드는데, 1로 끝나는 방법 : 0개
dp[2][2] = 1; // 2를 만드는데, 2로 끝나는 방법 : 1개 (2)
dp[3][1] = 1; // 3을 만드는데, 1로 끝나는 방법 : 1개 (2+1)
dp[3][2] = 1; // 3을 만드는데, 2로 끝나는 방법 : 1개 (1+2)
dp[3][3] = 1; // 3을 만드는데, 3로 끝나는 방법 : 1개 (3)
for (int i = 4; i <= 100000; i++) {
dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
}
}
int main() {
init();
cin >> T;
while (T--) {
cin >> N;
cout << ((dp[N][1] + dp[N][2]) % MOD + dp[N][3]) % MOD << '\n';
// 덧셈중 overflow가 발생할 수 있으므로, 두개씩 처리
}
return 0;
}
2. 쉬운 계단 수
45656과 같이, 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇개있는지 구하는 문제
예시
한자리수는 모두 계단수로 취급한다
두자리수부터
1
2
3
4
5
6
7
8
9
10 12
21 23
32 34
43 45
54 56
65 67
76 78
87 89
98
총 17개가 있다
이를 십의자리 수로 맞추는게 아닌, 일의자리수로 맞춰보면
1
2
3
4
5
6
7
8
9
10
(10)
(21)
(12, 32)
(23, 43)
(34, 54)
(45, 65)
(56, 76)
(67, 87)
(78, 98)
(89)
로 정렬할 수 있다
점화식
dp[i][j]를 i는 자리수, j는 마지막 자리수라고 하면 dp[2][1]은 1로 끝나는 2자리수의 개수라고 할 수 있다(1개)
1
2
3
4
5
6
7
8
9
10
dp[2][0] = 1 (10)
dp[2][1] = 1 (21)
dp[2][2] = 2 (12, 32)
dp[2][3] = 2 (23, 43)
dp[2][4] = 2 (34, 54)
dp[2][5] = 2 (45, 65)
dp[2][6] = 2 (56, 76)
dp[2][7] = 2 (67, 87)
dp[2][8] = 2 (78, 98)
dp[2][9] = 1 (89)
이를 통해 점화식을 뽑아내면
j로 끝나는 i자리수의 개수 = j-1로 끝나는 i-1자리수의 개수 + j+1로 끝나는 i-1자리수의 개수
dp[i][j] = dp[i-1][j-1] + dp[i+1][j+1] 로 표현할 수 있다
그런데 dp[i][0]은 dp[i-1][1]밖에 없고, dp[i][9] 또한, dp[i-1][8]밖에 없으므로 주의한다
소스코드
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
#include <iostream>
#define MOD 1000000000
using namespace std;
int dp[101][10];
int main() {
int N; cin >> N;
// 1의 자리수는 모두 1
for (int i = 1; i <= 9; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= 9; j++) {
if (j == 0) {
dp[i][0] = dp[i - 1][1];
}
else if (j == 9) {
dp[i][9] = dp[i - 1][8];
}
else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
}
}
}
int res = 0;
for (int i = 0; i <= 9; i++) {
res = (res + dp[N][i]) % MOD;
}
cout << res;
return 0;
}
dp 문제는 항상 점화식을 뽑아내는게 가장 어렵다