PS/BOJ

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

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

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

 

1535번: 안녕

첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번

www.acmicpc.net

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