백준 온라인 저지 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는 231-1보다 작거나 같은 자연수이다.

출력

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

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <iostream> #include <vector>   using namespace std; int dp[11] = {0, 1, 2, 4}; int n, k, cnt; vector<int> vec;   void solution(int sum) {     if (sum == n) {         cnt++;         if (cnt == k) {             cout << vec.at(0);             for (int i = 1; i < vec.size(); i++)                 cout << '+' << vec.at(i);             cout << '\n';         }         return;     }     for (int i = 1; i <= 3; i++) {         if (sum + i <= n) {             vec.push_back(i);             solution(sum + i);             vec.pop_back();         }     } }   int main() {       for (int i = 4; i <= 10; i++)         dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];     cin >> n >> k;     if (dp[n] < k)         cout << -1 << '\n';     else         solution(0);     return 0; }   Colored by Color Scripter

cs

 

먼저 k와 1,2,3으로 n을 만드는 경우의 수를 비교해서 k가 더 크면 -1을 출력한다.

 

solution함수는 재귀 방식으로 구현했고 벡터를 이용해서 풀었다.