[C++] BOJ 9095번: 1, 2, 3 더하기

문제 링크

문제 풀이

아래의 풀이에서는 입력받은 값과 관계없이 1부터 10까지의 수에 대한 1, 2, 3의 합으로 나타내는 방법의 수를 미리 계산하고 입력받은 값에 따라 계산해놓은 값을 출력하는 형태로 코드를 작성하였다. dp를 이용하여 문제를 해결하였다.

 

f(n)이 n이라는 수에 대한 1, 2, 3의 합으로 나타내는 방법의 수라고 하였을 때 다음 식이 성립한다.
f(n) = f(n-1) + f(n-2) + f(n-3) (n > 3), f(1) = 1, f(2) = 2, f(3) = 4

코드

#include <bits/stdc++.h>

using namespace std;

int calced[13];

int T;
int n;

void calcResult(int num)
{
    if (num > 10)
        return;
    if (num == 1)
        calced[1] = 1;
    else if (num == 2)
        calced[2] = calced[1] + 1;
    else if (num == 3)
        calced[3] = calced[1] + calced[2] + 1;
    else
        calced[num] = calced[num - 1] + calced[num - 2] + calced[num - 3];
    calcResult(num + 1);
}

int main(void)
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    calcResult(1);

    while (T--)
    {
        cin >> n;
        cout << calced[n] << '\n';
    }

    return 0;
}