[백준 - 15988] 1, 2, 3 더하기 3 [C++]

1. 문제

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

2. 풀이과정

n의 범위가 (1<=n<=1000000)이므로 n을 1, 2, 3의 합으로 나타내는 방법의 수를 

모두 구해보며 개수를 세는 방법은 시간초과가 발생한다.

 

점화식을 이용하여 다이나믹 프로그래밍으로 풀면된다.

dp[n] : n을 1, 2, 3의 합으로 나타내는 방법의 수

 

- 1을 1, 2, 3의 합으로 나타내는 방법들

 1

=> dp[1] = 1

 

- 2를 1, 2, 3의 합으로 나타내는 방법들

1 + 1

2

=> dp[2] = 2

 

- 3을 1, 2, 3의 합으로 나타내는 방법들

1 + 1 + 1

1 + 2

2 + 1

3

=> dp[3] = 4;

 

- 4를 1, 2, 3의 합으로 나타내는 방법들

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

=> dp[4] = 7; 

1+1+1+1, 1+2+1, 2+1+1, 3+1 이 식들은 3을 1, 2, 3의 합으로 나타내는 방법들에 1을 더해준 것이다.

1+1+2, 2+2 이 식들은 2를 1, 2, 3의 합으로 나타내는 방법들에 2을 더해준 것이다.

1+3 이 식은 1을 1, 2, 3의 합으로 나타내는 방법에 3을 더해준 것이다.

 

따라서 dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7이다.

확장해보면 dp[k] = dp[k-1] + dp[k-2] + dp[k-3] (k>=4)로 나타낼 수 있다.

 

[코드설명]

위의 설명을 그대로 구현한 코드이다.

 

3.코드 

#include <iostream>

using namespace std;
long long int dp[1000002];
int t;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i=4; i<=1000000; i++) {
        long long int sum = 0;
        for(int j=i-1; j>=i-3; j--) sum += (dp[j]%1000000009);
        dp[i] = sum;
    }
    cin >> t;
    for(int i=0; i<t; i++) {
        int num;
        cin >> num;
        cout << (dp[num]%1000000009) << "\n";
    }
    return 0;
}