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

문제 번호

• 15990(https://www.acmicpc.net/problem/15990)

문제 및 입/출력

정수 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일때 각각의 경우의 수를 구해서 최종적으로 합하는 점화식을 구성하였다.

 

 

 

소스 코드

#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;
}