[BOJ] 9095

1, 2, 3 더하기

9095번 https://www.acmicpc.net/problem/9095

분류

• Silver 3

• 다이나믹 프로그래밍

해법

어떤 수가 입력으로 들어왔을 때, 그 수를 1, 2, 3 으로 순서를 고려하여 나타낼 수 있는 경우의 수를 묻는 문제입니다.
초반에 몇 숫자만 구하다 보면
MakeBy123[n] = MakeBy123[n - 1] + MakeBy123[n - 2] + MakeBy123[n - 3] 임을 알 수 있습니다.

정답 코드

#include <iostream>
using namespace std;

int MakeBy123(int n)
{
    if (n == 1)
        return 1;
    else if (n == 2)
        return 2;
    else if (n == 3)
        return 4;
    else // n > 4
        return MakeBy123(n - 1) + MakeBy123(n - 2) + MakeBy123(n - 3);
}

int main(void)
{
    int T; // num of test cases
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int n;
        cin >> n;
        cout << MakeBy123(n) << endl;
    }
    return 0;
}