PS/BOJ

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

도비(Doby) 2022. 7. 4. 23:23

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

 

17845번: 수강 과목

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다.  이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이

www.acmicpc.net

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