9095번: 1, 2, 3 더하기

문제링크

C++

#include <iostream>

using namespace std;

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

    int T, n;
    cin >> T;

    int    arr[12];
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
    for (int i = 4; i <= 11; i++)
    {
        arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
    }

    for (int i = 0; i < T; i++)
    {
        cin >> n;
        cout << arr[n] << "\n";
    }
}

Python

import sys
input = sys.stdin.readline

T = int(input())

arr = [0] * 12
arr[1] = 1
arr[2] = 2
arr[3] = 4

for i in range (4, 12):
    arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]

for idx in range (1, T + 1):
    n = int(input())
    print(arr[n])

• 새 경우의 수를 이전 낮은 수의 경우의 수에서 구해낼 수 있는지 여부를 보고 dp풀이가 가능할 것 같아 보이는 것을 우선 생각하고,
• 실제 규칙성을 찾아낼 수 있었는지가 관건이었다.

어떤 수 n의 경우의 수를 구하는 것은 다음과 같이 볼 수 있다.

1) 맨 앞에 '1+'로 시작하는 경우의 수 : n - 1의 경우의 수만큼 존재
2) 맨 앞에 '2+'로 시작하는 경우의 수 : n - 2의 경우의 수만큼 존재
3) 맨 앞에 '3+'로 시작하는 경우의 수 : n - 3의 경우의 수만큼 존재

따라서 n의 경우의 수를 f(n)이라 하면 $f(n) = f(n - 1) + f(n - 2) + f(n - 3) \text{(}\forall n >3 \text{)}$의 점화식을 구할 수 있다.