728x90
반응형
1. 문제
https://www.acmicpc.net/problem/12101
2.풀이과정
문제의 설명대로 정수 n과 k가 주어졌을 때,
n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하면 된다.
4를 1, 2, 3의 합으로 나타내는 방법을 사전순으로 정렬하면 아래와 같다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 1+3
- 2+1+1
- 2+2
- 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;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 1051] 숫자 정사각형 [C++] (0) | 2021.03.14 |
---|---|
[백준 - 15988] 1, 2, 3 더하기 3 [C++] (0) | 2021.03.14 |
[백준 - 14500] 테트로미노 [C++] (0) | 2021.03.06 |
[백준 - 14501] 퇴사 [C++] (0) | 2021.02.14 |
[백준 - 15658] 연산자 끼워넣기 (2) [C++] (0) | 2021.01.26 |