[ boj : 4781 ] 사탕 가게

www.acmicpc.net/problem/4781

4781번: 사탕 가게

문제 : n종류의 사탕을 가지고 있고 m 원을 가지고 있을때 사탕을 가질 수 있는 최대무게를 구하여라

 

해설 : 

처음에 보고 그냥 냅색 문제구나 했지만,,,냅색문제와 가장 큰 차이점이 존재합니다. 바로 '갯수'입니다.

차근 차근 접근해 보면 일단 가장 단순하게 모든 경우의 수를 구하는 방법은 당연히 시간초과가 발생합니다.

그럼 우린 냅색문제를 푼 것처럼 접근해 봅시다.

dp[i][j] = i가지의 사탕을 선택하고 j원을 소비했을 경우에 가질 수 있는 최대 무게

라고 정의하고 평범한 냅색문제처럼 접근하면 이상함을 느낄 겁니다. 바로 이 문제에선 사탕의 개수가 무한정이라는 것 입니다. 그러면 현재 선택한 사탕의 가격을 하나씩 빼가면서 전의 정보에서 값들을 계산해 주면 되는거 아니냐 싶지만 그렇게 되면 O(nm^2) 으로 이 또한 시간초과가 발생합니다.

 

이를 어떻게 최적화 시켜야 할까요?

우린 이와 굉장히 비슷한 문제를 알고 있습니다.

www.acmicpc.net/problem/2294

2294번: 동전 2

바로 이 문제입니다. 만약 이 문제를 안푸셨다면 먼저 풀고 오세요.

 

어떻게 풀어야 될지 알게 되었으니 그 외의 것들을 고려해 주면 double형이 매우 거슬리니 100을 곱해서 int형으로 변환해 주고 싶은 욕구가 막 솟아납니다. 그러나 여기서 그치면 절대 안됩니다. 이유는 double 형은 부동소수점이니 실제 정확한 값이 들어가지 않기 때문이죠. 

그래서 전 어차피 소수점 2번째자리까지만 구하면 되니 0.005를 더해준 후 100을 곱해 int형으로 표현해 주었습니다.

 

#include<bits/stdc++.h>

using namespace std;

int n, m;
int dp[10010];

void solve();

int main()
{	
	double p;
	while (true) {
		cin >> n >> p;
		p += 0.005;
		m = p * 100;
		if (n == 0)break;
		solve();
		memset(dp, 0, sizeof(dp));
	}
	return 0;
}
void solve()
{
	int x,y;
	double input;
	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; i++) {
		cin >> x >> input;
		input += 0.005;
		y = input*100;
		v[i].first = x;
		v[i].second = y;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= m; j++) {
			if(j-v[i].second>=0)
				dp[j] = max(dp[j], dp[j - v[i].second]+v[i].first);
		}
	}
	cout << dp[m]<<"\n";
}