백준 - 4781 사탕가게

[문제 링크]

DP 문제이다. DP와 그리디 문제 예시로 유명한 '배낭 채우기'문제와 정말 유사한 문제이다.

배낭 채우기 문제와는 다른점은 메모이제이션 할 값이 실수형이라는 점인데, 여기서 소수 둘째자리까지만이라는 제한을 주었으므로,

이는 100을 곱해 자연수로 만든 후 처리가 가능하다.

다만 실수 자료형 부동소수점 문제로 오차가 있을 수 있으니 100을 곱한뒤 소수 첫째 자리에서 반올림해주어야 한다.

그렇게 변형한 금액으로 메모이제이션해 최대 값을 구하면 된다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
int n, c, cache[10001];
double m, p;
typedef pair<int, int> Candy;
Candy cd[5001];
int candyStore(int money) {
    int& ret = cache[money];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i <n; i++) {
        //남은 금액이 0 이상일 경우에만 비교. 
        if (money - cd[i].second >= 0) {
            int tmp = cd[i].first + candyStore(money - cd[i].second);
            ret = max(ret, tmp);
        }
    }
    return ret;
}
int main() {
    while (true) {
        memset(cache, -1, sizeof(cache));
        scanf("%d %lf", &n, &m);
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) {
            scanf("%d %lf", &c, &p);
            cd[i] = make_pair(c, (int)(p*100+0.5));
        }
        printf("%d\n", candyStore((int)(m*100+0.5)));
    }
}