PS/BOJ

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

도비(Doby) 2022. 6. 29. 23:42

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

 

16493번: 최대 페이지 수

첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이

www.acmicpc.net

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;
}