[백준 c++] 4781 사탕 가게

문제

https://www.acmicpc.net/problem/4781
사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다.
n개 줄에는 각 사탕의 칼로리 c와 가격 p가 주어진다.
상근이가 돈 m을 가지고 구매할 수 있는 가장 높은 칼로리를 출력하는 문제다.

---

풀이

5000가지 사탕을 선택하는 경우의 수를 구해야하는데, 심지어 중복해서 선택할 수 있기 때문에 단순히 풀면 시간초과가 나서 dp를 이용하여 풀어야한다
(따봉 dp야 고마워! 🦔)

1. 실수는 정수로 바꾸기

이 문제의 특징은 가격이 소수점 둘째자리까지의 실수형으로 주어진다는 것이다. (0.01 ≤ m ≤ 100.00)

그래서 처음엔 double로 입력받은 뒤, 100을 곱해서 정수형으로 바꾼 뒤 int 변수에 저장했다.

double m;
cin >> m;
int m2 = m*100;

그런데 100%까지 채점됐는데 틀렸다고 나왔다.

찾아보니까 double에 100을 곱해줄 때 오차가 있다는 것이다..
아니 도대체 무슨 오차? 55.89에 100 곱하면 5589 되는거 아닌가? 단순한거 아닌가? 하고 직접 돌려봤다.

    for (double i = 0.01; i <= 10; i += 0.01)
    {
        cout << i << " " << int(i * 100) << '\n';
    }

경악스럽게도 진짜 오차가 생긴다.

그래서 double을 쓰지않기로 했고, 모든 입력을 int로 받았고 마음이 편해졌다.
scanf("%d %d.%d", &n, &m1, &m2)

2. dp

dp[쓴 돈] = 칼로리
입력 받은 사탕의 칼로리가 c, 가격이 p일 때
이 사탕을 포함하는게 max값인가 아닌가를 판별해주면 된다.
이 사탕을 포함하는건 dp[j - p] + c

각각의 원소의 중복이 가능하기때문에 오름차순으로 for문을 돌린다.
for문의 범위는 현재 사탕 가격 p ~ 가지고있는 돈

for (int i = 0; i < n; i++){
	scanf("%d %d.%d", &c, &m1, &m2);
	p = m1 * 100 + m2;

	for (int j = p; j <= wallet; j++)
		{
			dp[j] = max(dp[j], dp[j - p] + c);
		}
}

---

코드

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n, m1, m2, wallet, c, p, dp[10001];
int main()
{
    while (1)
    {
        scanf("%d %d.%d", &n, &m1, &m2);
        if (!n && !m1 && !m2)
            break;
        wallet = m1 * 100 + m2;
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < n; i++)
        {
            scanf("%d %d.%d", &c, &m1, &m2);
            p = m1 * 100 + m2;

            for (int j = p; j <= wallet; j++)
            {
                dp[j] = max(dp[j], dp[j - p] + c);
            }
        }
        cout << dp[wallet] << "\n";
    }
}