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

풀이

1->1

2->1+1 / 2

3->1+1+1 / 1+2 / 3

4->1+1+1+1 / 1+1+2 2+2 / 1+3

5->1+1+1+1+1 / 1+1+1+2 1+2+2 / 1+1+3 2+3

6->1+1+1+1+1+1 / 1+1+1+1+2 1+1+2+2 2+2+2 / 1+1+1+3 1+2+3 3+3

7->1+1+1+1+1+1+1 / 1+1+1+1+1+2 1+1+1+2+2 1+2+2+2 / 1+1+1+1+3 1+1+2+3 1+3+3 2+2+3

1로만된거(무조건 1개)

마지막에 2로 더한거 ->dp[0][i]

마지막에 3을 더한거 ->dp[1][i]

출력: 1 + dp[0][n] + dp[1][n]

코드

#include <iostream>
using namespace std;

int dp[2][10001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    dp[0][2] = 1;
    for (int i = 3; i <= 10000; i++) {
        dp[0][i] = dp[0][i - 2] + 1;
        dp[1][i] = dp[0][i - 3] + dp[1][i - 3] + 1;
    }
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << 1+dp[0][n]+dp[1][n] << '\n';
    }
    
    return 0;
}

Written on March 14, 2019