[15989] 1, 2, 3 더하기 4

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

15989번: 1, 2, 3 더하기 4

<문제>

편의상 모든 경우의 수를 '오름차순'으로 가정하고 시작했다.

가령, 예제에 나온 4에 대한 조합은 아래의 4가지로만 계산하겠다는 의미이다.

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

위처럼 가정하면, "dp[i][j] : 마지막 수가 j일때 i를 만드는 경우의 수"로 초기화해줄때 아래의 점화식을 세울 수 있다. 

dp[i][1] = 1 // 1 + 1 + 1....이 i번 반복되는 경우가 유일

dp[i][2] = dp[i-2][1]+dp[i-2][2] // 3으로 끝나는 수는 전제에 맞지않으므로 배제하고 가져온다

dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3] // 3으로 끝나는건 아무 제약이 없다. 전부 가져오면 된다.

dp[i][0] = dp[i][1] + dp[i][2] + dp[i][3] // 빼도 되지만, 편의상 전체 경우의수를 dp[i][0]에 넣어두었다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int t, n, dp[10001][4];
int main(void) {
    int i;
    dp[1][1] = 1;
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[3][1] = 1;
    dp[3][2] = 1;
    dp[3][3] = 1;
 
    dp[1][0] = 1;
    dp[2][0] = 2;
    dp[3][0] = 3;
    for (i = 4; i <= 10000; i++) {
        dp[i][1] = 1;
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
        dp[i][3] = dp[i - 3][3] + dp[i - 3][2] + dp[i - 3][1];
        dp[i][0] = dp[i][1] + dp[i][2] + dp[i][3];
    }
    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][0] << '\n';
    }
    return 0;
}