백준 17485번: 수강 과목 (C++)

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

17845번: 수강 과목

---

Solved By: Knapsack DP

 

Knapsack DP 까먹기 방지용 문제^^

#include <iostream>
#include <vector>
#define pii pair<int, int>
using namespace std;

int n, k;
int cache[1001][10001];
pii subject[1001];

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