[백준 15988번] 1, 2, 3 더하기 3 (C++)

문제링크 : https://www.acmicpc.net/problem/15988

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000009;
ll dp[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int T;
    cin >> T;
    dp[1] = 1; dp[2] = 2; dp[3] = 4; //초기값
    for(int i=4; i<1000001; i++)
    {
        dp[i] = (dp[i-1]+dp[i-2]+dp[i-3]) %MOD; //점화식
    }
    while(T--)
    {
        int N;
        cin >> N;
        cout << dp[N] <<"\n";
    }
    return 0;
}

기본적인 DP 문제이다.

먼저 조합 대상 숫자인 1, 2, 3에 대해 초기화를 해준다.

dp[1] = 1 
dp[2] = 2 (1,1 / 2)
dp[3] = 4 (1,1,1 / 1,2 / 2,1 / 3)

이제 dp[4]의 경우를 보면 다음과 같다.

<N=4>
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2 
1 3
3 1

1 1 1 1  / 1 2 1 / 2 1 1 / 3 1의 경우를 보면 앞 숫자들의 합이 3이고 여기다가 + 1을 해준 것을 볼 수 있다.

앞의 숫자들의 조합은 dp[3]을 구할 때 봤던 조합들이고 여기에 + 1만 해준 것이기에 dp[3]의 값을 구해주면 된다.

 

1 1 2 / 2 2 의 경우를 보면 앞 숫자들의 합이 2이고 여기다가 + 2를 해준 것을 볼 수 있다.

앞의 숫자들의 조합은 dp[2]를 구할 때 봤던 조합들이고 여기에 + 2만 해준 것이기에 dp[2]의 값을 구해주면 된다.

 

1 3의 경우를 보면 앞 숫자가 1이고 뒤에 + 3을 해준 것을 볼 수 있다.

이 또한 dp[1]의 경우이기에 dp[1]의 값을 구해주면 된다.

 

따라서 dp[4]의 값은 dp[1] + dp[2] + dp[3]의 경우이다.

점화식의 경우 이러한 규칙이 반복되기에 dp[N] = dp[N-3] + dp[N-2] + dp[N-1]이 된다.