[Silver I] 1, 2, 3 더하기 2 - 12101

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 1월 3일 03:56:07

문제 설명

정수 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을 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;

int n, k;
vector<int> arr;
int ans = 0;
bool check = false;
void repeat(int cnt) {
	if (cnt > n) {
		return;
	}
	if (check) {
		return;
	}
	if (cnt == n) {
		ans++;
		if (ans == k) {
			for (int i = 0; i < arr.size()-1; i++) {
				cout << arr[i] << "+";
			}
			cout << arr[arr.size() - 1];
			check = true; //출력했으면 멈춤.
		}
		return;
	}
	for (int i = 1; i <= 3; i++) {
		arr.push_back(i);
		repeat(cnt + i);
		arr.pop_back();
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	repeat(0);
	if (!check) {
		cout << -1 << "\n";
	}
}

다른 사람 풀이.

[풀이 링크(뽕뽑기님)]

#include <bits/stdc++.h>
using namespace std;
int n,k;
vector <string> ans;
void backtracking(int idx,int m,int num,string op){
    if(idx == m){
        if (num == n) ans.push_back(op.substr(1,op.size()-1));
        return;
    }
    backtracking(idx + 1, m, num + 1, op + "+1");
    backtracking(idx + 1, m, num + 2, op + "+2");
    backtracking(idx + 1, m, num + 3, op + "+3");
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) backtracking(0,i,0,"");
    sort(ans.begin(),ans.end());
    if(ans.size() >= k) cout << ans[k-1];
    else cout << "-1";
}

다른 풀이를 찾아보던 중 개인적으로 마음에 들었던 풀이였다.