[백준] 9095번 - 1, 2, 3 더하기

문제

[9095번 링크]

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

풀이과정

(1) 규칙

정수n의 1,2,3의 조합이 몇개 들어가는지 확인합니다.

n=1	1 (1개)
n=2	11,2 (2개)
n=3	111,21,12,3 (4개)
n=4	1111,112,121,211,22,13,31 (7개)
n=5	11111,2111,1211,1121,1112,221,212,122,311,131,113,32,23 (13개)

이와같은 규칙으로 진행되므로, 점화식은 D[N] = D[N-1] + D[N-2] + D[N-3] 로 구할 수 있습니다.

메모이제이션을 이용하여 해결합니다.

(2) 순서

T와 정수n을 입력받고, 메모이제이션에 값을 저장하며 결과를 출력합니다.

(3) 코드

#include <iostream>
#include <list>
using namespace std;
int memo[12];
 
int main()
{
    long long T;
    list<int> v;
    cin >> T;
    while (T--)
    {
        int t;
        cin >> t;
        v.push_back(t);
    }
 
    memo[1] = 1;
    memo[2] = 2;
    memo[3] = 4;
 
    while (!v.empty())
    {
        for (int i = 4; i <= v.front(); i++)
        {
            memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];
        }
        cout << memo[v.front()] << endl;
        v.pop_front();
    }
 
    return 0;
}