[백준 15990] 1,2,3 더하기 5

문제 : 1,2,3 더하기 5

문제 유형 : 다이나믹 프로그래밍

일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자.

처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다.

3 + 1

1 + 3

2 + 2

2 + 1 + 1

1 + 2 + 1

1 + 1 + 2

1 + 1 + 1 + 1

여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.

이를 어떻게 풀까.......?

정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 

1. 3 + (n - 3)

2. 2 + (n - 2)

3. 1 + (n - 1)

1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.

3 + 1 + (n - 4)

3 + 2 + (n - 5)

2번에서 n - 2이 2가 아닌 1과 3으로 식을 전개하면 된다.

2 + 1 + (n - 3)

2 + 3 + (n - 5)

3번에서 n - 1이 1이 아닌 2와 3으로 식을 전개하면 된다.

1 + 2 + (n - 3)

1 + 3 + (n - 4)

이걸 어떻게 할까....?

1,2,3 더하기 4에서 내가 풀었던 방법처럼 이차원 배열을 만들어 채워보면 된다.

	1	2	3
1	1	0	0
2	0	1	0
3	1	1	1
4	2	0	1
5	1	2	1

직접 계산해보면서 채워보니 내가 생각했던 방법으로 하면 된다는 것을 깨닫게 되었다.

따라서 점화식으로 구해보면 아래와 같다.

이를 알고리즘에 바로 적용할 수 있도록 변형시키면 아래와 같다.

이를 이용하여 소스코드를 작성하면 아래와 같다.

#include<iostream>
 
using namespace std;
 
typedef long long ll;
const ll mod = 1000000009;
ll dp[100001][4];
 
ll solve(int n)
{
    if (dp[n][1] + dp[n][2] + dp[n][3] != 0)return (dp[n][1] + dp[n][2] + dp[n][3]) % mod;
    for (int i = 4; i <= n; i++)
    {
        if (dp[i][1] + dp[i][2] + dp[i][3] != 0)continue;
        for (int j = 1; j <= 3; j++)
        {
            ll sum = 0;
            for (int k = 1; k <= 3; k++)
            {
                if (k == j)continue;
                sum =(sum + dp[i - j][k] ) %mod;
            }
            dp[i][j] = sum;
        }
    }
 
    ll out = 0;
    out = (dp[n][1] + dp[n][2] + dp[n][3]) % mod;
    return out;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
    for (; T--;)
    {
        int input;
        cin >> input;
        cout << solve(input);
        if (T != 0)cout << '\n';
    }
    return 0;
}