4781번: 사탕 가게 
문제 링크: 4781번: 사탕 가게
개요
각 테스트케이스마다 사탕 n개의 칼로리와 가격이 주어졌을 때, m만큼의 돈으로 얻을 수 있는 최대 칼로리를 출력하는 문제이다. 0/1 배낭 문제의 형태를 띠고 있지만 각 사탕을 무제한으로 구매할 수 있고, 가격이 정수가 아니라는 점을 고려해야 한다.
풀이
n과 m 입력받기
1
2
3
int n, m; double tmp;
scanf("%d %lf", &n, &tmp);
m = (int)(tmp * 100 + 0.5);
이 문제에서 상근이가 가지고 있는 돈의 양 m은 소수점 둘째자리까지 주어지는 실수이다. 그러나 실수로는 dp를 수행하기 어렵기 때문에 100을 곱해 정수로 만들어서 사용했다.
int로 강제형변환 하기 전에 0.5를 더해서 값에 영향을 미치지 않되 부동소수 오차로 인해 잘못된 연산 결과가 나오는 경우를 방지했다.
사탕 정보 입력받기
1
2
3
4
5
pair<int, int> arr[MAX_N];
for (int i = 0; i < n; i++) {
scanf("%d %lf", &arr[i].first, &tmp);
arr[i].second = (int)(tmp * 100 + 0.5);
}
pair 배열에 각 사탕의 칼로리와 가격을 입력받았다. 여기서 가격은 위에서의 m과 마찬가지로 100을 곱해 정수로 만들어서 저장했다.
dp 수행하기
1
2
3
4
5
6
int dp[MAX_M + 1] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = arr[i].second; j <= m; j++) {
dp[j] = max(dp[j], dp[j - arr[i].second] + arr[i].first);
}
}
다이나믹 프로그래밍으로 배낭 문제를 수행할 것이다. dp[a]에는 돈을 a만큼 사용해서 얻을 수 있는 최대 칼로리이다(a는 100을 곱해 정수로 바뀐 상태이다).
i가 도는 반복문에서 모든 사탕을 순회하고, 사탕마다 j가 도는 반복문에서 사탕의 가격부터 가지고 있는 돈의 양만큼 순회하며 dp배열의 값을 변경한다. dp[j]의 값을 j보다 현재 사탕의 가격만큼 덜 썼을 때 얻는 최대 칼로리(dp[j - arr[i].second])에 현재 사탕의 칼로리(arr[i].first)를 더한 값으로 갱신하길 반복하며, 최종적으로 우리가 구하고자 하는 dp[m]을 얻는다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cmath>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_N 5000
#define MAX_M 10000
int main() {
int n, m; double tmp;
scanf("%d %lf", &n, &tmp);
m = (int)(tmp * 100 + 0.5);
while (n != 0 || m != 0) {
pair<int, int> arr[MAX_N];
for (int i = 0; i < n; i++) {
scanf("%d %lf", &arr[i].first, &tmp);
arr[i].second = (int)(tmp * 100 + 0.5);
}
int dp[MAX_M + 1] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = arr[i].second; j <= m; j++) {
dp[j] = max(dp[j], dp[j - arr[i].second] + arr[i].first);
}
}
printf("%d\n", dp[m]);
scanf("%d %lf", &n, &tmp);
m = (int)(tmp * 100);
}
return 0;
}