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

문제

 

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

문제

정수 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는 231-1보다 작거나 같은 자연수이다.

출력

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

---

Algorithm

백트레킹을 활용하여 합이 n보다 커지거나 재귀 깊이가 n보다 커지는 조건을 가진다면 합이 n이면 경우의 수를 나타내는 idx를 +1하고 이후 idx가 k랑 동일하다면 출력하고 종료 아닌경우 바로 종료하도록 하여 순열을 뽑아 나열하였다.만약 가능한한 모든  경우의수를 따진이후에도 경우의 수인 idx가k보다 작아 식이 없는 경우 main에서 -1을 따로 출력하도록 하였다.

 

---

 

 

Code

#include<iostream>
using namespace std;
int arr[11];
int idx=0;

void recur(int n,int k,int sum=0,int cnt=0);

int main(){
    int n,k;
    cin>>n>>k;
    recur(n,k);
    if(idx<k){
        cout<<-1;
    }
    return 0;
}

void recur(int n,int k,int sum,int cnt){
    if(sum>=n||cnt>=n){
        if(sum==n){
            idx++;
            if(idx!=k){
                return;
            }
            for(int i=0;i<cnt-1;i++){
                cout<<arr[i]<<'+';
            }
            cout<<arr[cnt-1];
        }
        return;
    }

    for(int i=1;i<=3;i++){
        arr[cnt]=i;
        recur(n,k,sum+i,cnt+1);
    }

}