boj 12101 1, 2, 3 더하기 2

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

12101번: 1, 2, 3 더하기 2

정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 사전순으로 정렬하여 k번째로 오는 식을 구하는 문제입니다.

 

먼저, N을 나타내는 방법의 수보다 k가 더 클수가 있기 때문에 dp배열에 N을 나타내는 방법의 수를 미리 저장하여 dp[N] < k이면 -1을 출력합니다.

 

다음은 문제 풀이 방법입니다.

예를들어, 4를 나타내는 방법은

1. 1+1+1+1

2. 1+1+2

3. 1+2+1

4. 1+3

5. 2+1+1

6. 2+2

7. 3+1

이렇게 7가지가 있는데, 여기서 1~4번은 3에서 1은 더한 것, 5~6번은 2에서 2를 더한 것, 7번은 1에서 3을 더한 것임을 알 수 있습니다. 이제 dp[N - 1]와 k를 비교합니다.

 

k가 5라고 하면, dp[4] = 7 > k = 5이므로 k번째 식이 있습니다.

그러면 dp[3]과 k를 비교합니다.

(n = 4)(dp[3] = 4) < (k = 5) 즉, 3에서 1을 더한 식이 아니므로 dp[2]과 k - dp[3]을 비교합니다. (n은 그대로 유지)

(n = 4)(dp[2] = 2) > (k = 1) 즉, 2에서 2를 더한 식이므로 식에 "2+"를 추가하고 그 다음 순서를 확인하기 위해 dp[1]과 k를 비교합니다. (n은 idx값인 2로 바뀜)

(n = 2)(dp[1] = 1) = (k = 1) 즉, 1에서 1을 더한 식이므로 식에 "1+"를 추가하고 그 다음 순서를 확인합니다.

(n = 1) n이 1이므로 식에 '1'을 추가하여 완성된 식을 출력하고 리턴합니다.

 

 

#include <iostream>
#include <string>
using namespace std;
 
int dp[11], N, K;
 
void init() {
    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];
    }
}
 
void func(int idx, int n, int k, string str) {
    if (n == 1) {
        str += '1';
        cout << str << '\n';
        return;
    }
    else if (n == 2 && k == 2) {
        str += '2';
        cout << str << '\n';
        return;
    }
    else if (n == 3 && k == 4) {
        str += '3';
        cout << str << '\n';
        return;
    }
 
    if (k > dp[idx]) {
        func(idx - 1, n, k - dp[idx], str);
    }
    else {
        str += (n - idx + '0');
        str += '+';
        func(idx - 1, idx, k, str);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    cin >> N >> K;
    if (dp[N] < K) {
        cout << "-1\n";
        return 0;
    }
    func(N - 1, N, K, "");
 
    return 0;
}