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

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

문제 : 1,2,3 더하기 2

이 문제는 1,2,3 더하기 문제를 이용해서 풀었다.

먼저 4를 본다고 하면 DP[3] + DP[2] + DP[1]를 더한게 DP[4]의 값이다. 아래 그림을 보며 이해를 하자.

4는 3 + 1, 2 + 2, 1 + 3인 경우의 수를 알 수 있고 이를 사전 순으로 정렬하면 1 + 3, 2 + 2, 3 + 1이렇게 된다.

따라서 4를 간단한 규칙으로 정리하면 1부터 DP[4-1]까지는 1로, DP[4-1] + 1부터 DP[4-1] + DP[4-2] 까지는 2로, DP[4-1] + DP[4-2] + 1부터 DP[4-1] + DP[4-2] + DP[4-3] 까지는 3으로 채워진다. 이런 방식으로 계산을 하면 원하는 구간에서 값을 계속 vector에 넣어 마지막에 출력하면 AC가 뜨는 간단한 문제이다. 하지만 이를 생각하는게 어려워 스타트가 어려운 문제이긴 하다.

#include<iostream>
#include<vector>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> vc;
ll dp[20];
 
ll k;
 
ll DP(int n)
{
    if (n <= 0)return 0;
    if (n == 1)return 1;
    if (dp[n])return dp[n];
    return dp[n] = DP(n - 3) + DP(n - 2) + DP(n - 1);
}
 
int cal(int n, ll begin, ll end)
{
    if (n == 0)return 0;
    ll f = dp[n - 1];
    ll s = dp[n - 2] + dp[n - 1];
    ll e = dp[n];
    if (n >= 1 && (begin < k && k <= begin + f))
    {
        vc.push_back(1);
        return cal(n - 1, begin, begin + f);
    }else if (n >= 2 && (begin + f < k && k <= begin + s))
    {
        vc.push_back(2);
        return cal(n - 2, begin + f, begin + s);
    }else if (n >= 3 && (begin + s < k && k <= begin + e))
    {
        vc.push_back(3);
        return cal(n - 3, begin + s, begin + e);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n >> k;
    dp[0] = dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    int vsize = DP(n);
 
    if (vsize < k)
    {
        cout << -1;
        return 0;
    }
 
    cal(n, 0, dp[n]);
 
    for (int i = 0; i < vc.size(); i++)
    {
        cout << vc[i];
        if (i < vc.size() - 1)cout << '+';
    }
 
    return 0;
}