[백준 12101번] 1, 2, 3 더하기 2 (C++)

문제링크 : https://www.acmicpc.net/problem/12101

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int n, k;
vector<string>v;

void func(int i, int idx, int sum, string tmp) //길이, 현재 인덱스, 누적합, 문자열 합
{
    if(idx==i) //목표 길이 도달
    {
        if(sum==n) v.push_back(tmp); //누적합도 일치하면 문자열 푸쉬 
        return; //목표 길이 도달했기에 리턴
    }
    func(i, idx+1, sum+1, tmp+"+1");
    func(i, idx+1, sum+2, tmp+"+2");
    func(i, idx+1, sum+3, tmp+"+3");
}


int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> n >> k;
    for(int i=1; i<=n; i++) func(i, 0, 0, ""); //최대 길이 n (1의 갯수 만큼)
    sort(v.begin(), v.end()); //정렬

    if(v.size()<k) cout << -1; //k번째 값이 존재하는지 체크
    else //k번째 값 출력
    {
        v[k-1].erase(0, 1); //맨 앞 + 제거
        cout << v[k-1];
    }
    return 0;
}

 

가능한 길이를 기준으로 재귀함수를 돌며 해당 길이당 가능한 문자열을 찾는다.

최대 길이는 1의 갯수에 따라 n개 까지 가능하다. (ex 4 = 1, 1, 1, 1)

 

기본적으로 인덱스를 재귀에 넘기며 해당 인덱스가 목표 길이에 도달하면 종료시키며,

종료 당시 누적합이 목표 합인 n과 같다면 재귀에 같이 넘겨줬던 문자열의 합을 따로 저장해준다.

재귀시 길이는 고정이므로 계속 같은 값을, 인덱스는 1개씩 늘어나므로 + 1을, 누적합의 경우 더해주는 값이 1, 2, 3이므로 각각 +1, +2, +3을, 문자열은 이에 맞게 +1, +2, +3을 문자열로 하여 더해주게 된다.

더해주는 값이 3가지이므로 재귀문에서 3개씩 돌아가게 된다.

 

이후 문제에 주어진 조건에 따라 저장된 문자열을 정렬해준다.

그리고 문자열의 크기가 k보다 작다는 것은 k번째 값이 존재하지 않다는 것이기에 -1을 출력하고,

아니라면 k번째 값을 출력해준다.

앞서 재귀함수에서 문자열을 더해줄때 +를 앞에다가 붙여서 같이 더해줬으므로 맨 앞의 +는 제거해주고 출력해줘야 한다.