백준 14728번: 벼락치기 (C++)

https://www.acmicpc.net/problem/14728

14728번: 벼락치기

---

Solved By: Knapsack DP

 

시간을 무게라고 두고, 배점을 가치라고 두었을 때, Knapsack DP를 돌려서 최대 이득 배점을 구해내면 됩니다.

#include <iostream>
using namespace std;

int cache[101][10001];
pair<int, int> test[101];
int n, t;

int main(){
    cin >> n >> t;
    
    for(int i = 1; i <= n; i++){
        cin >> test[i].first >> test[i].second;
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= t; j++){
            if(test[i].first <= j){
                cache[i][j] = max(cache[i - 1][j], test[i].second + cache[i - 1][j - test[i].first]);
            }
            else{
                cache[i][j] = cache[i - 1][j];
            }
        }
    }
    
    cout << cache[n][t];
    return 0;
}