[C++] 백준 1535 안녕

https://www.acmicpc.net/problem/1535
제목 : 안녕
난이도 : Silver II

풀이

배낭 문제와 풀이가 똑같다!
라이프가 100부터 시작하지만 0이 되는 순간도 기쁨을 느낄 수 없기 때문에 최대 라이프를 99로 두고 0이 될 때도 포함하여 계산 해도 된다.

예시를 들어보겠다.
총 라이프가 7이고 4명의 사람이 있다고 가정하자.

그리고 라이프를 계산할 테이블을 만든다.
라이프가 0이 되거나 음수가 될 때의 기쁨은 느끼지 못하기 떄문에 최대 라이프에서 1을 뺀 라이프 값 까지만 적었다.
(가로 : 라이프, 세로 : 사람 번호)

현재 라이프가 0 일때는 아무에게도 인사를 나눌 수가 없어 전부 0 이다.

현재 라이프가 1일때 1번 사람은 요구하는 라이프가 1이므로 우리는 인사를 하여기쁨을 느낄 수 있다.
라이프가 2, 3, 4, ... , 6일때도 마찬가지다.

2번 사람은 요구하는 라이프가 3 이다. 라이프가 1, 2 일때는 이 사람과 만나도 기쁨을 느낄 수 없기 때문에 이전 사람까지의 기쁨값을 가지고 내려온다.

하지만 요구하는 라이프가 3부터는 이 사람과도 인사를 하여 기쁨을 느낄 수가 있기 때문에
현재 사람과 인사를 했을 때의 기쁨 값과 인사를 안했을 때의 기쁨 값을 비교해서 큰 값을 넣어야 한다.

현재 사람과 인사를 안하면 이전 사람들과 인사한 기쁨 값을 가지고 오면 되고,
현재 사람과 인사를 하려고 하면 이전에 인사할 때
(현재 라이프 - 요구 라이프) 만큼 남았을 때 이전 사람과 인사를 한 후의 기쁨 값에 현재 사람의 기쁨값을 더하면 된다.

식은 이렇게 나온다.

max(
table[이전사람][현재 라이프],
table[이전사람][현재 라이프 - 현재 사람 요구 라이프]
)

그렇게 계산하면 표는 이렇게 작성이 된다.

이후 나머지를 이어가면 아래의 표 처럼 나온다.

최종적으로 우리가 출력해야 하는 값은 기쁨의 최대치이기 때문에
마지막 사람까지 인사를 건냈을 때의 최대값을 구하면 되므로

table[마지막 번호][최대라이프]

값을 출력하면 된다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, life, fun;
    cin >> N;
    vector<int> lifes, funs;
    vector<vector<int>> dp(N + 1, vector<int>(100, 0)); // 가로 : 개수, 세로 : 라이프
    for (int i = 0; i < N; i++) {
        cin >> life;
        lifes.push_back(life);
    }
    for (int i = 0; i < N; i++) {
        cin >> fun;
        funs.push_back(fun);
    }

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < 100; j++) {
            if (i == 0 || j == 0) continue;
            else if (lifes[i - 1] <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - lifes[i - 1]] + funs[i - 1]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[N][99];
}