백준 16943번: 최대 페이지 수 (C++)

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

16493번: 최대 페이지 수

---

Solved By: Knapsack DP

 

 

#include <iostream>
using namespace std;

pair<int, int> chapter[21];
int cache[21][201];
// 일 수 == 무게, 페이지 수 == 가치
int n, m;

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