백준 15988, 1, 2, 3 더하기 3

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

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

입력

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

출력

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

예제 입력 1 

3
4
7
10

예제 출력 1 

7
44
274

 

 다이나믹 프로그래밍 유형 중 전형적인 문제이다. 3 가지 경우로 나누어서 끝이 1을 더하여 끝나는 경우, 2를 더하여 끝나는 경우, 3을 더하여 끝나는 경우로 나누어 주어진 수가 1 일 때부터 입력받은 수들 중 가장 큰 수까지 연쇄적으로 구하였다. 알고리즘은 다음과 같다.

 

1. 테스트 케이스 개수와 각각의 데이터를 입력받는다.
2. dp[1][0] ~ dp[3][2] 까지 입력을 받는다. (나는 메모리를 아끼기 위해 [k][0], [k][1] , [k][2]에 대해 합이 k이고 각각 마지막으로 1, 2, 3을 더한 경우를 저장하였다. 직관적으로 하고 싶다면 두번째 인덱스 사이즈를 4로 정하고 1, 2, 3 인덱스에 저장해도 된다. )
3. 연쇄적으로 dp 배열을 채워나간다. dp[k][0]에 대해서 dp[k-1][0] + dp[k-1][1] + dp[k-1][2], dp[k][1]에 대해서 dp[k-2][0] + dp[k-2][1] + dp[k-2][2], dp[k][2]에 대해서 dp[k-3][0] + dp[k-3][1] + dp[k-3][2] 을 집어 넣는다. 수가 커질 것을 대비해서 미리 모듈러 연산을 추가한다.
4. 입력 n에 대해 경우 수는 dp[n][0] + dp[n][1] + dp[n][2] 이고 이를 출력한다.  

 

  코드는 다음과 같다.

 

#include <iostream>
#include <vector>

long long dp[1000001][3]; // [k][0] : 마지막이 1, [k][1] : 마지막이 2, [k][2] : 마지막이 3

int main()
{
    int N;
    std::cin >> N;

    std::vector<int> input;

    int max_num = -1;
    for (int i = 0; i < N; i++)
    {
        int data;
        std::cin >> data;
        input.push_back(data);

        if (data > max_num) max_num = data;
    }

    dp[1][0] = 1;
    dp[1][1] = 0;
    dp[1][2] = 0;

    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[2][2] = 0;

    dp[3][0] = 2;
    dp[3][1] = 1;
    dp[3][2] = 1;

    if (max_num > 3)
    {
        for (int i = 4; i <= max_num; i++)
        {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 1000000009;
            dp[i][1] = (dp[i - 2][0] + dp[i - 2][1] + dp[i - 2][2]) % 1000000009;
            dp[i][2] = (dp[i - 3][0] + dp[i - 3][1] + dp[i - 3][2]) % 1000000009;
        }
    }

    for (int i = 0; i < input.size(); i++)
    {
        std::cout << (dp[input[i]][0] + dp[input[i]][1] + dp[input[i]][2]) % 1000000009 << '\n';
    }

    return 0;
}

 

 이 것으로 글을 마친다.