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

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

github : https://github.com/junho0956/Algorithm/blob/master/12101/12101/%EC%86%8C%EC%8A%A4.cpp

 

기본 9095번같은 경우 dp를 사용했었지만 사실 n의 사이즈가 dp를 사용하지 않아도 되는 문제입니다.

이 문제의 경우 dp를 사용하지 않고, dfs간에 string 을 추가시켜주면서 해결하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<string> v;
 
int dfs(int num, string str) {
 
    if (num < 0) return 0;
    if (num == 0) {
        v.push_back(str);
        return 1;
    }
 
    int res = 0;
 
    for (int i = 1; i <= 3; i++) {
        res += dfs(num - i, str+=(i+'0'));
        str.pop_back();
    }
 
    return res;
}
 
int main() {
    int n, k; cin >> n >> k;
    dfs(n, "");
    sort(v.begin(), v.end());
 
    if (k > v.size()) cout << "-1";
    else {
        string ans = "";
        for (int i = 0; i < v[k-1].size(); i++) {
            ans += v[k-1][i];
            ans += '+';
        }
        ans.pop_back();
        cout << ans;
    }
    return 0;
}