백준12101 - 1, 2, 3 더하기 2

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

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

n까지의 1, 2, 3으로 만들 수 있는 합의 경우의 수를 구한 뒤 k번째에 오는 경우를 출력하면 되는 문제이다.

 

n을 만들기 위한 1, 2, 3의 더하기 합의 경우의 수 점화식은 다음과 같다.

d[n] = d[n - 1] + d[n - 2] + d[n - 3]

 

n을 만들 때 가장 숫자가 많은 경우는 최대 n개이다. 1로 n개를 이용하여 만들면 되기 때문이다.

 

k번째 수를 찾는 과정은 bfs를 이용하여 탐색한다.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#define MAX 11
using namespace std;

int n, k;
int d[MAX] = { 0, };

vector<string> ans;

//경우의 수 덧셈 찾기
void find() {
	queue<string> q; //탐색할 숫자를 저장할 공간
	map<string, bool> mp; //방문 여부

	//처음에 1, 2, 3을 넣고 방문처리
	q.push("1");
	q.push("2"); 
	q.push("3");
	mp["1"] = true;
	mp["2"] = true;
	mp["3"] = true;

	while (!q.empty()) {
		int sum = 0; //현재까지 뽑은 원소의 합

		//제일 첫번째 원소를 뽑고 삭제
		string s = q.front(); 
		q.pop();

		//현재까지 뽑은 숫자를 더한다.
		for (int i = 0; i < s.size(); i++) {
			sum = sum + (s[i] - '0');
		}
		
		//현재까지 뽑은 숫자가 n인 경우 벡터의 삽입
		if (sum == n) {
			ans.push_back(s);
			continue;
		}

		//현재까지 뽑은 숫자의 합이 길이가 n보다 긴 경우는 무시
		if (s.size() > n) {
			continue;
		}
		
		//숫자는 1, 2, 3으로 이루어짐, 각 경로를 탐색
		for (int i = 1; i <= 3; i++) {
			if (s.size() == n) { //길이가 n이면 더 이상 더해도 n보다 커지니까
				continue; //무시
			}
			string temp = s;
			temp = temp + char('0' + i); //숫자의 끝에 i를 삽입
			if (!mp[temp]) { //방문하지 않은 숫자면
				q.push(temp); //큐에 넣고
				mp[temp] = true; //방문처리
			}
		}
		
	}

}
int main() {
	cin >> n >> k;

	//10까지의 더하기 가짓수 찾기
	d[1] = 1;
	d[2] = 2;
	d[3] = 4;
	for (int i = 4; i <= 10; i++) {
		d[i] = d[i - 1] + d[i - 2] + d[i - 3];
	}

	if (d[n] < k) { //n을 만들 수 있는 경우의 수보다 많은 수를 물어보면
		cout << -1;
	}
	else { //n을 만들 수 있는 경우의 수안에서 물어보면
		find(); //숫자를 찾는다.
		sort(ans.begin(), ans.end()); //오름차순으로 정렬

		//k번째 수를 +를 포함하여 출력
		for (int i = 0; i < ans[k - 1].size(); i++) {
			cout << ans[k - 1][i];
			if (i == ans[k - 1].size() - 1) {
				break;
			}
			cout << "+";
		}
	}
}