[C++/BOJ] 백준 12101 1,2,3더하기2 (백트래킹)

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

 

 

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

백준티어 : 실버1

 

입력

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

출력

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

예제 입력 1 복사

4 3

예제 출력 1 복사

1+2+1

 

 

=> n과 k가 입력될때 총 합이 n이 되는 1,2,3의 합으로 이루어진 식의 k번째 식을 출력하는 문제이다.

 

해설 :

 

백트래킹을 이용해서 1,2,3의 합으로 이루어진 벡터를 구한후 전역변수 cnt를 이용해 번호를 센다.

그 번호(cnt)가 k가 될때 출력하도록 함수를 구현한다.

 

 

 

정답 코드 :

#include<iostream>

#include<vector>

using namespace std;

int n, k, cnt;

void func(vector<int>& v, int sum) {

    if (sum > n) return;  //sum(합)이 n보다 크다면 필요없으므로

    if (sum == n) {

            cnt++; // 개수를 1증가시켜준다.

                if (cnt == k) { //k번째라면

                       for (int i = 0; i < v.size(); i++) {  //1,2,3으로 이루어진 벡터를 크기만큼(전체)를 출력

                                 if (i == v.size() - 1) cout << v[i]; // 마지막 숫자를 출력할때는 "+"기호를 붙이지않는다.

                                 else cout << v[i] << "+";

                       }

               }

           return; 

    }

    for  (int i = 1; i <= 3; i++) { // 1,2,3으로 이루어지므로

            v.push_back(i);  //i를 넣는다.

            func(v, sum + i); // sum에 i를 더하고 다시 함수를 실행한다.

            v.pop_back(); 

    }

}

int main() {

     ios::sync_with_stdio(0); cin.tie(0);

      cin >> n >> k;

      vector<int> v;

      func(v, 0);  // 인수로 vector와 0을 넣어준다. // 현재 합(sum)은 0이기 때문이다.

     if (cnt == 0 || cnt < k) cout << "-1";  // 합의 개수가 0개 즉, 없거나 k개보다 적은 경우 -1을 출력한다.

}

 

 

자세한 설명은 주석을 참고해주세요.

 

문제 후기 :

백트래킹에 조금 익숙해진것같다.

함수의 인수에도 vector<int>& v이 들어갈수있다는것을 처음 알게되었다.

백트래킹 공부하기에 괜찮은 문제라고 생각한다.