BOJ 9095 1, 2, 3 더하기

boj 9095 1, 2, 3 더하기

D[i] = 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수라고 하자. 앞 부분은 겹치는 부분이므로 맨 마지막에 올 수 있는 1, 2, 3의 경우만 살펴보면 된다.

• n = n-1 + 1 -> n-1을 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 1을 붙이는 경우
• n = n-2 + 2 -> n-2를 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 2를 붙이는 경우
• n = n-3 + 3 -> n-3을 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 3을 붙이는 경우

D[i]는 위 세 가지 경우의 합이다. 그러므로 점화식을 D[i] = D[i-1] + D[i-2] + D[i-3]로 설정하고 구현한다.

#include <iostream>
using namespace std;

int t;
int D[15];

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

    cin >> t;

    D[0] = 0;
    D[1] = 1;
    D[2] = 2;
    D[3] = 4;

    for (int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        for (int i = 4; i < 11; i++)
        {
            D[i] = D[i - 1] + D[i - 2] + D[i - 3];
        }
        cout << D[n] << '\n';
    }
}