[백준 1535번] 안녕 (C++)

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

1535번: 안녕

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int L[21], J[21];
int dp[21][101];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;
    for(int i=1; i<=N; i++) cin >> L[i]; //체력
    for(int i=1; i<=N; i++) cin >> J[i]; //기쁨

    for(int i=1; i<=N; i++)
    {
        for(int j=0; j<=100; j++)
        {
            if(j-L[i]>0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]]+J[i]);
            else dp[i][j] = dp[i-1][j];
        }   
    }

    cout << dp[N][100];

    return 0;
}

DP 배낭 문제이다.

가능한 체력 내에서 최대한의 기쁨을 더해주면 된다.

 

주의해야할 것은 체력이 0이나 음수가 되면 기쁨이 0이 되는 것이다.

따라서 j-L[i]>=0이 아닌 j-L[i]>0으로 체력이 0이하가 되지 않도록 해주었다.

 

주어진 인원수 N에 체력 최대치 100이내에 최대한의 기쁨을 찾는 것이므로 dp[N][100]을 출력해주면 된다.