[15990] 1, 2, 3 더하기 5(C++)

문제

바로가기

정수 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로 나눈 나머지를 출력한다.

 

 

🌱 해결 방법

[9095] 1, 2, 3, 더하기의 응용 버전

[9095] 1, 2, 3 더하기(Top-down & Bottop-up)

 

4를 1, 2, 3의 합으로 나타낼 수 있는 모든 경우의 수는 아래와 같고

그 중 문제의 조건에 해당하는 경우는 빨간색이다.

 

4를 문제의 조건을 만족시키면서 1, 2, 3으로 나타내는 방법은

3 + (1을 1, 2, 3의 합으로 나타낸 경우)
2 + (2을 1, 2, 3의 합으로 나타낸 경우)
1 + (3을 1, 2, 3의 합으로 나타낸 경우)

이렇게 크게 3가지가 있다.

 

하지만 문제에서 1, 2, 3중 같은 수를 연속으로 두 번 이상 쓸 수 없다고 했기 때문에

저기서 경우를 한 번 더 나눠줘야 한다.

가지치기로 나타내면 아래와 같다.

 

n을 1, 2, 3의 합으로 나타낸 경우 중 1, 2, 3으로 끝나는 경우의 수를 각각 dp[n][1], dp[n][2], dp[n][3]이라고 하면

이렇게 나타낼 수 있고 점화식은 아래와 같다.

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

정답 = dp[n][1] + dp[n][2] + dp[n][3]

 

 

❗️ 주의할 점

모든 경우의 수를 계속 더해나가기 때문에 dp에 저장되는 값이 어느 순간부터 기하급수적으로 커질 수 있다. 

1. dp의 자료형은 unsigned int 또는 long long으로 할 것

2. 정답을 출력할 때 뿐만 아니라 값을 중간 저장할 때도 1,000,000,009로 나눈 나머지 값을 저장하기

 

 

🌿 내 코드(C++)

// [15990] 1, 2, 3 더하기 5
// https://www.acmicpc.net/problem/15990
// dp
// 배열 자료형 주의

#include <iostream>
using namespace std;

unsigned int dp[100001][4];

// n을 1, 2, 3의 합으로 나타내는 방법의 수
void go(int n)
{
    for(int i = 4 ; i <= n ; i++) {
        if(dp[i][1] == 0) { // 구한 적이 없다면
            dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1000000009;
            dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1000000009;
            dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1000000009;
        }
    }  
}

int main(void)
{
    int t, n; 
    cin >> t;
    dp[1][1] = 1, dp[1][2] = 0, dp[1][3] = 0;
    dp[2][1] = 0, dp[2][2] = 1, dp[2][3] = 0;
    
    for(int i = 1 ; i <= 3 ; i++) {
        dp[3][i] = 1;
    }

    while(t--) {
        cin >> n;
        go(n);
        cout << (dp[n][1] + dp[n][2] + dp[n][3]) % 1000000009 << '\n';
    }
}