[백준][C++] 9095, 15988: 1,2,3 더하기 (dp)

문제

---

9095

15988

1, 2, 3의 합으로 나타내는 방법을 구하는 문제들.

풀이

---

완전탐색으로 경우의 수를 전부 세볼 수 있지만

이 문제는 특정한 규칙을 찾아야하는 문제이다.

• 1 : 1
• 2 : 1 + 1, 2
• 3 : 1 + 1 + 1, 2 + 1, 1 + 2 , 3
• 4 : [3] + 1, [2] + 2, [1] + 3

이렇게 나열해보면 n에서의 경우의 수는

• [n-1]의 경우의 수 에서 각각에 1을 붙인것
• [n-2] ‘’’ 2를 붙인것
• [n-3] ‘’’ 3을 붙인것

을 전부 합한것으로 볼 수 있다.

즉 점화식은 다음과 같다.

$dp[n] = dp[n-1] + dp[n-2] + dp[n-3]$

코드

---

#include <iostream>

using namespace std;

int n;
int cached[12];

void init()
{
    cached[0] = 1;
    cached[1] = 1;
    cached[2] = 2;
    for(int i = 3; i < 11; i++) {
    cached[i] = cached[i - 1] + cached[i - 2] + cached[i - 3];
    }
}


int main()
{
    init();
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        cout<<cached[n]<<"\n";
    }
}