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

알고리즘 분류 : 다이나믹 프로그래밍(DP)

문제 : 1, 2, 3 더하기

이 문제는 계산을 어떻게 할껀지 점화식을 세우면 금방 푸는 문제이다. 난 이 문제를 풀면서 재귀적인 풀이를 생각하며 풀었다.

5라는 숫자가 있을 때, 여기서 1, 2, 3을 뺀 숫자들 4, 3, 2가 1, 2, 3의 합으로 나타내는 경우의 수를 다 더하면 된다는 것을 발견하였다. 이를 수식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]이다. 여기서 n을 1, 2, 3을 빼다 보면 DP[0]인 경우가 나온다. 이럴 때, DP[0]의 값을 뭐로 하면 좋을까? 간단한 예를 보자.

2라는 숫자가 있다. 2라는 숫자는 보자마자 1 + 1와 2로 경우의 수가 나온다. 이를 내가 푼 방식으로 한번 보자.

2는 1, 2, 3으로 뺐을 때 1, 0, -1이 나온다. 일단 여기서 -1이 나온건 경우의 수에 포함 될 수 없으므로 -1일 때 경우의 수는 0이다. 1은 경우의 수에 포함 될 수 있다는 것을 알 수 있다. 0을 보면 2 - 2에서 나온 값이다. 2는 2 + 0로 표현 가능하다. 여기서 + 0은 생략가능하므로 2는 그냥 2인 것이다. 즉 0인 것은 n이 1,2,3 일 때 자기 자신도 경우의 수로 포함 시켜준다. 

따라서 이를 정리하여 식으로 써보면

이를 참고하여 소스코드를 짜 보면 아래와 같다.

반복문으로 풀 수 있지만 재귀로 푸는게 이해하기 

#include<iostream>
 
using namespace std;
 
int dp[1000] = { 0 };
 
int solve(int n)
{
    if (n < 0)return 0;
    if (n <= 1)return 1;
    if (dp[n])return dp[n];
    return dp[n] = solve(n - 3) + solve(n - 2) + solve(n - 1);
}
 
int main()
{
    int T;
    cin >> T;
    for(;T--;)
    {
        int n;
        cin >> n;
        cout << solve(n) << '\n';
    }
}