[백준 - 12101] 1, 2, 3 더하기 2 [C++]

1. 문제

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

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

2.풀이과정

문제의 설명대로 정수 n과 k가 주어졌을 때,

n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하면 된다.

 

4를 1, 2, 3의 합으로 나타내는 방법을 사전순으로 정렬하면 아래와 같다.

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

[코드설명]

dfs함수는 n을 1, 2, 3의 합으로 나타내는 경우의 수를 생성하며 k번째로 오는 식을 출력한다.

 

3. 코드

#include <iostream>
#include <vector>

using namespace std;
int n, k, cnt;

void dfs(vector<int>& v, int sum) {
    if(sum > n) return ;
    if(sum == n) {
        cnt++;
        if(cnt == k) {
            for(int i=0; i<v.size(); i++) {
                if(i==v.size()-1) cout << v[i];
                else cout << v[i] << "+";
            }
            exit(EXIT_SUCCESS);
        }
        return ;
    }
    for(int i=1; i<=3; i++) {
        v.push_back(i);
        dfs(v, sum+i);
        v.pop_back();
    }
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    vector<int> v;
    dfs(v, 0);
    if(cnt == 0 || cnt<k) cout << "-1";
    return 0;
}