[백준] 4781번 사탕가게

문제 링크: https://www.acmicpc.net/problem/4781

문제

입출력

문제 접근

dp문제이다.
일반적인 dp문제랑 다를 거 없다. 사탕을 나온 순서대로 현재 가격에서 칼로리 최대치와 현재 가격에서 현재 사탕가격을 빼고, 현재 사탕 칼로리를 더한 값중에 큰 것을 저장하면 된다.
cache[j] = max(cache[j], cache[j-candy_money[i]] +cal[i] )

코드 구현(c++)

#include <iostream>
#include <cstring>

using namespace std;

int n;
int m;
float M;
int cal[5001];
int money[5001];
int cache[10001];

int dp(){
    int maxCal = -1;
    for(int i = 0 ; i < n ; i++){
        for(int j = money[i] ; j <= m ; j++){
            cache[j] = max(cache[j], cache[j-money[i]] + cal[i]);
            maxCal = max(maxCal, cache[j]);
        }
        
    }
    return maxCal;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    float temp_money;
    while(1){
        cin >> n >> M;
        if(n==0) break;
        m = M*100;
        memset(cal, 0, sizeof(cal));
        memset(money, 0, sizeof(money));
        memset(cache, 0, sizeof(cache));
        for(int i = 0 ; i < n ; i++){
            cin >> cal[i] >> temp_money;
            money[i] = temp_money*100;
        }
        cout << dp() << "\n";
    }
}