백준 1082: 방 번호

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

 

일단 문제를 보아하니 DP 문제인 것 같다.

내가 DP 문제를 풀 때 먼저 생각하는 것이 있다. "일단 먼저 가보자, 그리고 그 상태를 숫자로 나타내서 결과값을 저장하자"이다. 이러한 방식으로 나는 플레티넘 DP 문제도 해결해왔다.

 

그런데, 이 문제는 뭔가 다른 것 같다. 아무리 생각해도 이전에 고른 숫자를 DP하는 방법이 떠오르지 않았다. 최대 숫자가 long long 타입을 넘을 위험성이 있어서, string 타입을 사용해야하는데, 이것을 DP 배열의 인덱스로 바꾸는 법이 도저히 떠오르지 않았고, 해쉬테이블 사용은 불안했다.

 

결국 나는 생각을 전환하기로 한다. DP에서 벗어나서, Greedy한 생각으로 방침을 바꾸기로. 이 문제에서 최대 숫자는 어떤 숫자일까? 일단 떠오르는 것은 길이다. 최대 숫자가 어떤건지는 모르겠지만, 길이가 가장 길 것이다. 여기까지 생각하자 번뜩 머리에 스쳐가는 아이디어가 있었다.

 

나는 이전에 고른 숫자를 고려했었다. 그런데, 내가 아무리 높은 숫자를 고르더라도, 길이가 짧으면 말짱 도루묵이다. 그러면 길이가 가장 긴 숫자를 구하고, 내림차순으로 Sort하면, 내가 원하는 답이 나올 것이다. 즉, 내가 DP를 할 것은 가장 큰 숫자가 아닌 가장 큰 숫자의 길이다. 길이를 DP하고 Reconstruct하는 과정을 거치면 답이 나온다고 생각을 했다.

 

여기까지 하고 문제를 해결하고 싶지만, 아직 고려해야할 사항이 남았다. 첫째, 방번호는 0이 아닌 이상 0으로 시작할 수 없다. 즉, 0으로만 이루어진 길이 2 이상의 방번호는 불가능하다. 나는 이것을 dp에 새로운 차원을 추가해서 해결하였다.

기존의 DP가 

 

DP[남은 돈] = 숫자의 최대 길이

 

라고 한다면, 이번에 새롭게 정의한 것은

 

DP[남은 돈][처음인가?] = 숫자의 최대 길이

 

이다. 즉, 처음에만 0을 넣을 수 없게 하도록, 설계를 하면 된다. 이러면 적어도 0으로만 이루어진 숫자는 성립될 수 없다. 하지만, 숫자가 0인 경우, 바로 빈 문자열을 반환하므로, 이에대한 예외처리가 필요하다. 다행히 문제에 적어도 하나의 숫자를 살 수 있는 입력만 주어진다 라 명기되어 있어서, 예외처리가 수월하다.

 

둘째, 길이가 같은 수가 여러 개일 때, 어떤 수를 골라야하나? 이 경우는 비교적 쉽게 해결할 수 있다. reconstruct를 할 때, N - 1 부터 0까지 순회하면 된다. 이러면 큰 수부터 들어가서, 가장 큰 숫자가 될 수 있다. reconstruct를 할 때 주의점은 일단 해당 함수에서 답을 구했다면 바로 break를 걸어서 함수를 나와야한다. 그렇지 않으면 다른 숫자가 섞여서 들어갈 위험이 있다. 예전에 풀었던 DP 문제에서 이게 문제가 되어서, 몇 달 동안 그 문제의 해결에 전전긍긍했던 경험이 있다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, P[10], dp[51][2];
string ans = "";
int solve(int money, bool f)
{
	int& ret = dp[money][f];
	if (ret >= 0) return ret;
	ret = 0;
	for (int i = f; i < N; i++)
		if(money >= P[i])
			ret = max(ret, solve(money - P[i], false) + 1);
	return ret;
}

void reconstruct(int money, bool f)
{
	for (int i = N - 1; i >= f; i--)
		if (money >= P[i] && dp[money][f] == dp[money - P[i]][0] + 1)
		{
			ans.push_back(i + '0');
			reconstruct(money - P[i], false);
			break;
		}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 0; i < N; i++) cin >> P[i];
	cin >> M;
	solve(M, true);
	reconstruct(M, true);
	sort(ans.begin(), ans.end());
	reverse(ans.begin(), ans.end());
	if (ans.empty()) ans = "0";
	cout << ans << '\n';
}

그리디한 생각이 필요한 재미있는 DP 문제였다.