[BOJ] 12101 : 1,2,3 더하기 2

12101 : 1,2,3 더하기 2

풀이

dp[1] = 1

dp[2] = 1+1 2

dp[3] = 1+1+1 1+2 2+1 3

dp[4] = 1+1+1+1 1+1+2 1+2+1 1+3 / 2+1+1 2+2 / 3+1

처음에는 마지막이 1,2,1,3 반복되는것으로 풀어볼까 하다가…

dp[4]를 볼때 1부터 시작하는것이 dp[3]개 있고,

2부터 시작하는것이 dp[2]개, 1부터 시작하는것이 dp[1]개 있다.

미리 DP로 값을 계산 해둔 후(1,2,3더하기1참고)

이 규칙을 이용해서 재귀함수로 필요한 값을 구했다.

코드

#include <iostream>
using namespace std;

long long dp[11];

void go(int n,int k) {
    if (n == 1) {
        cout << "1";
        return;
    }
    else if (n == 2) {
        if (k == 1) {
            cout << "1+1";
        }
        else {
            cout << "2";
        }
        return;
    }
    else if (n == 3 && k==4) {
        cout << "3";
        return;
    }

    if (dp[n - 1] >= k) {
        cout << "1+";
        go(n - 1, k);
    }
    else if (dp[n - 1] + dp[n - 2] >= k) {
        cout << "2+";
        go(n - 2, k - dp[n - 1]);
    }
    else {
        cout << "3+";
        go(n - 3, k - dp[n - 1] - dp[n - 2]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= 10; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    int n, k;
    cin >> n>>k;
    if (k > dp[n]) {
        cout << -1;
        return 0;
    }
    go(n,k);
    return 0;
}

Written on March 14, 2019