1, 2, 3 더하기 9095

문제

접근 방법

0의 경우 NULL (없지만 적어두자) 0개이지만 1개로 본다. (어차피 n이 0일 가능성은 없다.)
1의 경우 1 1개
2의 경우 1+1 2 2개
3의 경우 4개

1+1+1 2+1 (2의 경우)
1+2 (1의 경우)
3 (0의 경우)

4의 경우 7개

1+1+1+1 2+1+1 1+2+1 3+1 (3의 경우)
1+1+2 2+2 (2의 경우)
3+1 (1의 경우)

5의 경우 13개

1+1+1+1+1 2+1+1+1 1+2+1+1 3+1+1 1+1+2+1 2+2+1 3+1+1 (4의 경우)
1+1+1+2 2+1+2 1+2+2 3+2 (3의 경우)
1+1+3 2+3 (2의 경우)

n의 경우는 (n-1의 경우+n-2의 경우+n-3의 경우)임을 알 수 있다.
중복되지 않게 경우의 수를 늘리기 위해 1, 2, 3만큼 부족한 경우에서 더한다고 볼 수 있다.

6의 경우를 예측해보자.
5의 경우+ 4의 경우+ 3의 경우일 것이다.
즉 24개

7의 경우는 44개로 예측된다. 실제로 예제 출력도 44개이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    vector<int> dp(11);
    dp[0] = dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= 10; ++i)
    {
        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
    }
    while (T--)
    {
        int n;
        cin >> n;
        cout << dp[n] << "\n";
    }
    return 0;
}

풀이

dp[n]=dp[n-3]+dp[n-2]+dp[n-1]이라는 것을 도출해내면 쉬운 문제이다.