[백준/BOJ] 4781 사탕 가게

문제 : 4781 사탕 가게

4781번: 사탕 가게

사탕가게에 있는 모든 사탕의 가격과 칼로리가 주어질 때,

보유한 금액 내에서 칼로리합이 가장 크도록 사탕을 사는 문제이다.

같은 사탕을 여러 개 살 수 있기 때문에 DP 알고리즘을 사용해서 배열을 채우면 된다.

입력으로 주어지는 실수를 정수로 바꿀 때

오차가 날 수 있으므로 반올림을 위해서 0.5를 더한 후 바꾼다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, arr[10005];
double m;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (1){
        fill(&arr[0],&arr[10004],0);
        cin >> N >> m;
        M=(ll)(m*100+0.5);
        if (N==0 && M==0)
            break;
        for (ll i=0;i<N;i++){
            ll a, b;
            double c;
            cin >> a >> c;
            b=(ll)(c*100+0.5);
            for (ll j=1;j<=M;j++){
                if (j>=b){
                    arr[j]=max(arr[j],arr[j-b]+a);
                }
            }
        }
        cout << arr[M] << "\n";
    }
    return 0;
}