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

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

---

문제)

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

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

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 2^31-1보다 작거나 같은 자연수이다.

 

 

 

출력 :

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int n, k;
vector<string> vec;
 
void recur(int cur, vector<int> record)
{
    if (cur > n) return;
 
    if (cur == n)
    {
        string temp = "";
        for (auto x : record)
        {
            temp += to_string(x);
        }
        vec.push_back(temp);
        return;
    }
 
    for (int i = 1; i < 4; i++)
    {
        record.push_back(i);
        recur(cur + i, record);
        record.pop_back();
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> k;
 
    recur(0, vector<int> ());
 
    sort(vec.begin(), vec.end());
 
    if (vec.size() < k)
    {
        cout << -1;
    }
    else
    {
        for (int i = 0; i < vec[k - 1].length(); i++)
        {
            cout << vec[k - 1][i];
            if (i != vec[k - 1].length() - 1) cout << "+";
        }
    }
}
 

---

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

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