[백준] 1535번 안녕 C++ 코드

코드

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, happy[23], sad[23],dp[23][103];

int go(int idx, int hp) {
    if(hp <= 0) return -987654321; // 체력이 0이 되면 사망
    if(idx == n) return 0;
    if(dp[idx][hp] != -1) return dp[idx][hp];
    int include = go(idx + 1, hp - sad[idx]) + happy[idx]; // 인사를 하는 경우
    int exclude = go(idx + 1, hp); // 인사를 하지 않는 경우
    dp[idx][hp] = max(include, exclude);
    return dp[idx][hp];
}

int main() {
    cin >> n;
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < n; i++) cin >> sad[i];
    for(int i = 0; i < n; i++) cin >> happy[i];
    cout << go(0,100) << '\n'; // 체력은 100부터 시작
    return 0;
}

풀이

0 - 1 냅색문제랑 비슷한 유형이다. 인사를 하거나 하지 않는 경우를 나눠서 생각했다. 인사를 한다면 체력을 깎고 행복을 올린다. 인사를 하지 않으면 다음 케이스로 넘어간다. 만약 체력이 0이하가 되면 매우 작은 값을 리턴한다. 마지막 사람까지 만난 경우, 체력이 남아있을 때 최대 행복을 출력한다.