백준 Gold 3 방 번호

방 번호 (백준 Gold 3)

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

n개의 가격이 주어지며
각 가격은 0~n-1 까지의 ‘번호’를 가지고 있다
그리고 M원이 주어질때
주어지는 M원을 통해 만들 수 있는 ‘가장 큰 번호’를 구하는 문제

풀이 방법

M원을 가능한 사용하여
최대한 큰 번호를 구해야 함

따라서 ‘이전’에 구했던 ‘수’들에
새로운 수를 더하는 방식으로 다시 숫자를 얻을 수 있기에
나는 dp 문제라 생각하였다

• dp[n] : n원을 소모하여 얻을 수 있는 가장 큰 숫자
  

또한 Bottom-up을 이용하여 문제를 풀었다

• dp[0] 부터 주어지는 ‘가격’을 더하여
  마지막에 존재하는 dp[money]를 구하는 방식
  

다만 생각해볼 점은

• 가능한 ‘많은 자릿수’를 얻으면 좋다
  (다만 첫 자리가 0인 경우는 “0”으로 해석)
  

• 자릿수가 같다면 ‘큰 수’를 저장해야 한다
  

• 또한 String을 reverse 정렬하여
  ‘가장 큰 수’을 임의로 만들어 줄 수 있다
  

위와 같은 부분에서
‘비교용’ 함수를 만들어 주었다
(사실 이러한 판단 조건이 존재하기에 ‘그리디’하다 볼 수 있을 것 같다)

제출 코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

string comp(const string& a, const string& b)
{
	if (a.size() != b.size())
	{
		if (a.size() > b.size())
			return a;

		return b;
	}

	if (a > b)
		return a;

	return b;
}

int main()
{
	int n;
	cin >> n;
	vector<int> costs(n);
	for (int i = 0; i < n; i++)
	{
		cin >> costs[i];
	}

	int money;
	cin >> money;

	vector<string> dp(money + 1,"");

	for (int i = 0; i <= money; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i + costs[j] <= money)
			{
				string a = dp[i] + to_string(j);
				sort(a.rbegin(), a.rend());
				if (a[0] == '0')
					a = "0";
				dp[i + costs[j]] = comp(dp[i + costs[j]], a);
			}
		}
	}

	cout << dp[money];

	return 0;
}

결과

처음에는 ‘배낭 문제’의 응용인줄 알았으나
자세히 보니 ‘숫자’를 중복 구매 할 수 있는 상황이었다

그렇기에 Bottom-up 방식으로 접근하여 문제를 풀 수 있었다