문제

정수 n을 1, 2, 3의 합으로 나타내는 모든 방법을 사전순으로 정렬했을 때, k번째에 오는 식을 구하면 된다.

• 입력: n k.
• 출력: 사전순 k번째 식. 방법의 수가 k보다 적으면 -1.
• 제한: n이 작다(≤ 11).

접근

n이 작으니 굳이 영리할 필요 없이 백트래킹으로 모든 식을 직접 만들어 본다.

지금까지의 합에 1, 2, 3을 차례로 더해 가며, 합이 n이 되면 그 조합을 식 문자열로 만들어 저장한다. 합이 n을 넘으면 그 가지는 버린다. 더하는 순서를 1 → 2 → 3(작은 수부터)으로 두면, 만들어지는 식들이 자연스럽게 사전순으로 쌓인다.

다 모은 뒤 k번째를 출력하고, 개수가 모자라면 -1. (아래 코드는 인덱스를 맞추려고 맨 앞에 더미 "0"을 하나 넣고 ans[k]를 출력한다.)

풀이

전체 코드: thxwelchs/algorithm

#include <bits/stdc++.h>

using namespace std;

int n, k;

// vector<string> v;
vector<int> v;
vector<string> ans;

void backtrack(int sum) {
    if(sum >= n) {
        string s = "";
        s += (char) (v[0] + '0');
        for(int i = 1; i < v.size(); i++) {
            s += "+";
            s += (char) (v[i] + '0');
        }

        // cout << s << '\n';
        ans.push_back(s);

        return;
    }

    for(int i = 1; i <= 3; i++) {
        if(sum + i > n) {
            continue;
        }
        v.push_back(i);
        backtrack(sum + i);
        v.pop_back();
    }
}

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

    cin >> n >> k;

    ans.push_back("0");
    backtrack(0);

    if(k > ans.size() - 1) {
        cout << - 1;
        return 0;
    }

    cout << ans[k];

    return 0;
}