BOJ(C++) / 백준 12101 : 1, 2, 3 더하기 2

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

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

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 더하기 2 12101
#include <iostream>
#include <string>
#include <map>

using namespace std;

int N, K;
int arr[3] = { 1,2,3 };
map<string, int> m; //사전순으로 정렬됨

//DFS로 N의 합을 나타냄
void DFS(string s, int sum) {
	for (int i = 0; i < 3; i++) {
		sum += arr[i];
		if (sum > N)
			continue;
		else if (sum == N)
			m[s + to_string(arr[i])]++; //n의 합을 맵에 저장
		else
			DFS(s + to_string(arr[i]) + "+", sum); // "+"와 함께 저장
		sum -= arr[i];
	}
}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;

	DFS("", 0);

	//k번째에 오는 식이 없을 때
	if (K > m.size()) {
		cout << "-1" << "\n";
		return 0;
	}

	int i = 0;
	for (auto it : m) {
		i++;
		if (i == K) {
			cout << it.first << "\n"; //K번째에 오는 수 찾기
		}
	}

	return 0;
}
//걸린 시간 40분

 

설명

DFS를 이용하여 n을 나타낼 수 있는 방법을 모두 구하여 map에 저장하였다.

map은 사전 순으로 정렬된다는 특징이 있다.

합이 n보다 크다면 범위를 벗어났으므로 continue 한다.

합이 n과 같다면 n을 구하는 방법 중 하나 이므로 map에 수를 string형으로 변환하여 저장한다.

합이 n보다 작다면 string형으로 변환하여 +와 함께 다음 DFS로 넘겨준다. 

n을 나타낼 수 있는 방법을 모두 구하였다면 k번째에  오는 것을 출력한다. 

고찰

걸린 시간 : 40분

DP문제라는 것을 알고 DP로 문제를 풀려고 했지만 n을 1,2,3의 합으로 나타낼 수 있는 개수만 알 수 있었고 K번째에 오는 수를 알 수는 없었다. 그래서 n을 나타낼 수 있는 방법을 모두 구하여 값을 출력할 수 있었다. 

 

난이도

Silver 1