[BOJ/Gold 4] 백준 29756 DDR 체력 관리(C++)

문제 링크

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

29756번: DDR 체력 관리

 

문제

리듬게이머 코더빡은 최근 댄스 댄스 레볼루션(DDR)에 푹 빠져있다. 이 게임은 곡이 재생될 때 떨어지는 노트에 맞춰 발판을 밟는 게임으로, 많은 체력을 소모하기 때문에 체력 관리가 매우 중요하다.

곡은 N개의 구간으로 이루어져 있고, 어떠한 구간 i (1 ≤ i ≤ N)에 대해 코더빡은 해당 구간을 플레이할지, 포기할지 선택할 수 있다. 해당 구간을 플레이할 때 얻을 수 있는 점수는 si점이며, 체력을 hi만큼 소모한다. 구간을 포기할 때는, 점수를 얻지 못하고 체력도 소모하지 않는다.

곡이 시작할 때, 코더빡은 체력 100을 가지고 시작한다. 매 구간에 진입하기 전에 체력을 K만큼 회복한다. 이 체력 회복은 구간을 플레이하거나 포기하는 것과는 무관하게 일어남에 유의하라. 회복 후 코더빡의 체력이 100을 초과하는 경우 체력이 100이 되며, 구간을 플레이했을 때 체력이 0 미만으로 하락하는 경우 코더빡은 해당 구간을 포기해야만 한다.

하루 종일 DDR을 밟아 기진맥진인 코더빡은 더 이상 체력 관리를 위한 판단을 내릴 수 없다. 코더빡이 성과를 뽑아낼 수 있도록 그가 얻을 수 있는 최대 점수를 알려주는 프로그램을 작성하시오.

지문에서 언급하지 않은 게임오버 등의 시스템은 이 문제에서 고려하지 않는다.

 

입력

첫 번째 줄에는 두 정수 N과 K가 공백으로 구분되어 주어진다. N은 곡의 전체 구간의 수를 의미하며, K는 회복하는 체력의 양이다. (1 ≤ N ≤ 1,000; 1 ≤ K ≤ 10)

두 번째 줄에는 정수 s1, s2, ⋯, sN이 공백으로 구분되어 주어진다. (1 ≤ si ≤ 1,000)

세 번째 줄에는 정수 h1, h2, ⋯, hN이 공백으로 구분되어 주어진다. (1 ≤ hi ≤ 100)

 

출력

코더빡이 얻을 수 있는 최대 점수를 출력한다.

 

예제 입력 1

10 10
1 2 3 4 5 6 7 8 9 10
9 9 9 9 9 9 9 9 9 9

예제 출력 1

55

 

모든 구간을 플레이할 수 있다.

예제 입력 2

5 10
70 90 80 100 60
60 60 60 60 60

예제 출력 2

190

 

세 구간 이상을 플레이하는 방법은 없다. 90점짜리 구간을 플레이한 후 체력이 40이 되며, 1개의 구간을 포기하고 체력을 2번 회복해 100점짜리 구간을 플레이하는 방법으로 최대 점수인 190점을 얻을 수 있다.

 

알고리즘 분류

• 배낭 문제

 

풀이

배낭 문제도 Top-Down 방식으로 해결할 수 있다는 것을 이 문제로 처음 알게 되었다.

N번째 구간부터 체력 100을 갖고 시작한다.

매번 구간을 진입할 때마다 K만큼의 체력을 회복하고 시작하는데, 체력이 100을 초과하게 되면 100으로 고정시킨다.

그리고 현재 구간을 플레이할 때 필요한 H만큼의 체력을 깎고도 체력이 0 미만으로 내려가지 않는다면 현재 구간을 플레이했을 때의 점수와 플레이하지 않았을 때의 점수를 비교한다. 체력이 0 미만이 된다면 현재 구간은 플레이하지 않고 건너뛴다.

N개의 구간을 모두 탐색하게 되면 재귀를 종료한다.

처음에 반드시 체력이 100인 상태로 시작해야 하기 때문에 Top-Down 방식을 사용하는 것이 정답인 것 같다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX_N 1001
#define MAX_H 101
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, K;
int S[MAX_N], H[MAX_N];
int DP[MAX_N][MAX_H];
int Answer;

void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> S[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
    }
}

int top_Down(int Depth, int Health) {
    if (Depth == 0) {
        return 0;
    }

    int NextHealth = min(Health + K, 100);
    if (DP[Depth][NextHealth] != 0) {
        return DP[Depth][NextHealth];
    }

    int Result = top_Down(Depth - 1, NextHealth);
    if (NextHealth - H[Depth] >= 0) {
        Result = max(Result, top_Down(Depth - 1, NextHealth - H[Depth]) + S[Depth]);
    }

    return DP[Depth][NextHealth] = Result;
}

void settings() {
    Answer = top_Down(N, 100);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}