백준, boj) 4781. 사탕 가게(C / C++)

1. 문제 링크

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

4781번: 사탕 가게

2. 문제 설명

사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하자.

 

3. 문제 힌트

돈의 양이 소수점인데, 100을 곱해서 자연수로 만들어주자.

그럼 배낭문제랑 똑같다. 

 

dp[n]는 n원을 썼을 때 얻을 수 있는 최대 값으로 정의하자.

그러면 만약에 dp[n]에서 100원짜리를 고른다고 할 때,

dp[n] = max(dp[n], dp[n-100] + 100원의 가치) 이렇게 식을 세울 수 있다.

n-100원에서의 최댓값 + 100원의 가치 하면 최댓값의 후보 1개를 구할 수 있다.

 

4. 문제 풀이

알고리즘은 (3)에서 다 서술한 것 같다.

 

문제는 자연수로 바꾸는데 부동소수점의 문제가 있다는 것이다.

float로 선언해서 잘 풀었다.

 

그냥 다른 사람의 풀이가 궁금해서 찾아봤는데 모두 double로 한 다음 0.5를 더해서 뭐 오류를 없애야 한다던데.. 잘 알아보지는 않았다.

float로 하니 그런 문제가 없었다.

 

5. 코드

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m;
float f;

int main()
{
	scanf("%d %f", &n, &f);
	m = f * 100;

	while (!(n == 0 && m == 0)) {

		int dp[10001] = { 0 };
		pair<int, int> v[5001];	//c, v;

		for (int i = 1; i <= n; ++i)
		{
			float temp;
			scanf("%d %f", &v[i].second, &temp);
			v[i].first = temp * 100;
		}
		sort(v + 1, v + n + 1);

		for (int i = 1; i <= m; ++i)
			for (int j = 1; j <= n; ++j) {
				if (i - v[j].first < 0)break;
				dp[i] = max(dp[i], dp[i - v[j].first] + v[j].second);
			}
		printf("%d\n", dp[m]);

		scanf("%d %f", &n, &f);
		m = f * 100;
	}


	return 0;
}

6. 결과 사진