백준 1535번: 안녕 (C++)

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

1535번: 안녕

---

Solved By: Knapsack DP

 

여전히 Knapsack DP 공부 중..

#include <iostream>
using namespace std;

int cache[21][101];
pair<int, int> human[21];
// first == 체력, second == 기쁨
int n;

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