백준/DP

[백준 15990, c++] 1,2,3 더하기 5(dp:bottomUp)

전두선 2019. 12. 8. 16:32
문제 번호
문제 및 입/출력

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

  • 1+2+1
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

 

예제 입력1
3
4
7
10
예제 출력1
3
9
27

 

문제 풀이

앞서 풀었던 BOJ 9095(1,2,3 더하기 1), BOJ 15988(1,2,3 더하기 3)에서 변형된 문제이다. 

주어진 입력 n을 1,2,3의 합으로 나타내는데 같은 수를 두 번 이상 연속해서 사용하면 안된다는 조건이 붙어있다.

 

우선 조건을 따지지 않고, 정수 n을 1,2,3 합으로 나타낼 수 있는 모든 경우의 수를 구해보았다.

n 1,2,3 조합
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+1+1

2+2

3+1

... ...

결과적으로 

n=1일때 1씩 증가할떄마다 1,2,3,7 ... 로 증가하게 되고,

점화식은 d[n] = d[n-1] + d[n-2] + d[n-3]이 되었었다.

 

n 1,2,3 조합(+ 조건을 따졌을때)
1 1
2

2

3

1+2

2+1

3

4

1+2+1

1+3

3+1

5

1+3+1

2+1+2

2+3

3+2

...

....

 

이번 문제에서는 추가 조건(연속으로 같은 숫자를 사용불가)로 인해 

마지막으로 오는 수가 1이면? 그 앞에 올 수 있는 숫자는 2 또는 3이 된다.
마지막으로 오는 수가 2이면? 그 앞에 올 수 있는 숫자는 1 또는 3이 된다.
마지막으로 오는 수가 3이면? 그 앞에 올 수 있는 숫자는 1 또는 2이 된다.

라는 규칙을 갖고 문제를 풀 것이다.  

 

점화식은 이차원 배열로 구성이 되고,

D[n][i]마지막에 오는 수가 i일 때, 1,2,3의 합으로 정수 n을 만드는 경우의 수가 된다.

 

D[n][1] = D[n-1][2] + D[n-1][3]

D[n][2] = D[n-2][1] + D[n-2][3]

D[n][3] = D[n-3][1] + D[n-3][2]

-> result = D[n][1] + D[n][2] + D[n][3]

 

위 처럼 정수 n에 제일 마지막에 오는 숫자가 1,2,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
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
typedef long long ll;
 
const int mod = 1e9 + 9;
const int MAXN = 100000;
ll dp[MAXN+1][4];
 
void solve(void) {
    dp[1][1= dp[2][2= dp[3][1= dp[3][2= dp[3][3= 1;
    for (int n = 4; n <= MAXN; n++) {
        if (n - 1 >= 0) {
            dp[n][1= (dp[n - 1][2+ dp[n - 1][3]) % mod;
        }
        if (n - 2 >= 0) {
            dp[n][2= (dp[n - 2][1+ dp[n - 2][3]) % mod;
        }
        if (n - 3 >= 0) {
            dp[n][3= (dp[n - 3][1+ dp[n - 3][2]) % mod;
        }
    }
}
 
int main() {
    int t;
    scanf("%d"&t);
 
    solve();
    while (t--) {
        int n;
        scanf("%d"&n);
        printf("%d\n", (dp[n][1+ dp[n][2+ dp[n][3]) % mod);
    }
    return 0;
}