백준 1535 - 안녕(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1535

1535번: 안녕

N명이 사람이 있을 때, i번째 사람에게 인사를 하면 L[i]만큼 체력이 줄어들고, J[i]만큼 기쁨이 늘어납니다.

이때, 최대로 얻을 수 있는 기쁨을 구하는 문제입니다.

 

사람의 수가 <= 20이기에 모든 경우를 확인해도 시간초과가 되지 않습니다. (2^1 + 2^2 + .... 2^20 < 1억)

-> 따라서 확인할 수 있는 모든 경우를 확인했습니다.

 

i번째 사람을 선택하는 경우와 안하는 경우가 있기 때문에 이를 모두 vector에 넣어준 뒤, 

선택하는 경우에서 최댓값을 비교해주면 됩니다.

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
int L[21], J[21];
vector<pair<int, int>> dp[21];

void solve(){
    int maxi = 0;
    if(100 - L[1] > 0){
        dp[1].push_back({100-L[1], J[1]});
        maxi = max(maxi, J[1]);
    }
    dp[1].push_back({100, 0});
    for(int i = 2; i <= N; i++){
        for(int j = 0; j < dp[i-1].size(); j++){
            dp[i].push_back(dp[i-1][j]);
            if(dp[i-1][j].first - L[i] > 0){
                dp[i].push_back({dp[i-1][j].first - L[i], dp[i-1][j].second + J[i]});
                maxi = max(maxi, dp[i-1][j].second + J[i]);
            }
        }
    }
    cout << maxi;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> L[i];
    for(int i = 1; i <= N; i++) cin >> J[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.