BOJ 1082 - 방 번호

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1471	361	285	26.316%

문제

---

이번에 VIP 회장으로 새로 부임한 백은진은 빅뱅의 위대함을 세계에 널리 알리기 위해서 사무실을 하나 임대했다.

빅뱅은 위대하기 때문에, 사무실의 번호도 되도록이면 커야 한다고 생각한다. 따라서 지금 가지고 있는 돈 전부를 가지고 방 번호를 만들려고 한다.

1층에 있는 문방구에서는 숫자를 판다. 각 숫자의 가격은 서로 다를 수 있기 때문에, 현재 가지고 있는 돈을 이용해서 만들 수 있는 가장 큰 숫자를 만들려고 한다.

예를 들어, 문방구에서 파는 숫자가 0, 1, 2이고, 각 숫자의 가격이 6, 7, 8이고, 백은진이 현재 가지고 있는 돈이 21이라면, 백은진이 만들 수 있는 가장 큰 수는 210(8+7+6=21)이다.

입력

---

문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 예를 들어, N=4이면, 문방구에서 파는 숫자는 0,1,2,3인 것이다. 둘째 줄에 각 숫자를 사는데 드는 비용이 작은 숫자부터 주어진다. 이 비용은 50보다 작거나 같은 자연수이다. 마지막 줄에는 백은진이 현재 가지고 있는 돈이 주어진다. 돈은 50보다 작거나 같은 자연수이다.

출력

---

첫째 줄에 백은진이 가지고 있는 돈으로 만들 수 있는 가장 큰 수를 출력한다. 백은진이 가지고 있는 돈은 적어도 숫자 하나는 살 수 있기 때문에, 답은 항상 존재한다.

0을 제외하고 0으로 시작하는 수는 없다.

접근

---

문제를 보면 바로 DP로 풀어야 된다는 것을 알 수 있다.
다만, 평소 DP 문제와는 다르게 long long의 범위도 넘어가서 string으로 풀어야 된다.
길이가 더 길거나, 길이는 같은데 앞자리수가 더 큰 문자열이 더 크다고 생각하면 된다.

풀이

---

우선 comp 함수를 만들어서 string의 대소 비교 처리를 해주었다.
dp[i] 에는 i원으로 만들수 있는 가장 큰 문자열을 만든다.
다만, "0000"과 같은 문자열이 들어가지 않게 예외처리를 해준다.
string을 sort를 활용하면 손쉽게 내림차순으로 정렬할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, money;
int arr[10];
string dp[51], ans = "0";

bool comp(string a, string b)
{
	if (a.length() > b.length()) return true;
	else if (a.length() == b.length() && a > b) return true;
	else return false;
}

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

	CIN(N);
	FUP(i, 0, N - 1) CIN(arr[i]);
	CIN(money);
	FUP(i, 0, money) dp[i] = "";
	FUP(i, 1, money)
	{
		FUP(j, 0, N - 1)
		{
			if (i - arr[j] < 0) continue;
			string tmp = dp[i - arr[j]] + (char)('0' + j);
			sort(tmp.rbegin(), tmp.rend());
			if (tmp.front() == '0') continue;
			if (comp(tmp, dp[i])) dp[i] = tmp;
		}
		if (comp(dp[i], ans)) ans = dp[i];
	}
	COUT(ans);

	return 0;
}