[백준 C++] 30407번 나비의 간식을 훔쳐먹은 춘배

30407번: 나비의 간식을 훔쳐먹은 춘배

문제 요약

문제

춘배가 나비의 간식을 뺏어 먹고 도망가자 화난 나비는 냥냥펀치를 날리려 한다.

냥냥펀치 : 문제에서 주어진 $R_i$에서 춘배와 나비 사이의 거리를 뺀 값만큼 춘배의 체력이 깎인다. 데미지가 $10$이고 현재 춘배와 나비 사이의 거리가 $3$일 경우 $7$만큼 체력이 깎인다. 체력이 깎이는 양은 음수가 될 수 없다.

춘배는 도망가다 상자를 발견해서 숨게 되었고 자신이 가진 $3$가지 기술로 대응하려 한다.

• 웅크리기: 나비가 공격할 시 데미지가 절반 감소한다. 이는 데미지가 거리만큼 약해진 후 계산된다. 단, 감소 후 데미지의 소수점 아래는 버린다.
• 네발로 걷기: 문제에서 주어진 값 $K$ 만큼 나비와 멀어지는 방향으로 이동할 수 있다.
• 깜짝 놀라게 하기: 나비의 다음 행동을 $1$번 무시한다. $i$번째 사용 할 시 $R_{i+1}$를 무시한다. 단 $1$번 사용할 수 있고 $N$번째에 사용 시 아무 일도 일어나지 않는다.

한 턴은 춘배의 기술, 냥냥펀치, 데미지 계산의 순서대로 실행된다. 춘배는 턴마다 $1$개의 기술만 쓸 수 있다. 나비가 모든 $N$개의 냥냥펀치를 하여 지칠 때까지 춘배가 유지할 수 있는 최대 체력을 알아보자. 어떤 행동을 해도 체력이 $0$이하가 된다면 $-1$을 출력한다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫 번째 줄에 나비가 지칠 때까지의 냥냥펀치 수 $N$이 정수로 주어진다. $(1 \le N \le 18)$  두 번째 줄에 춘배의 체력 $H$, 현재 나비 사이의 거리 $D$, 춘배가 네발로 걷기 시 이동하는 거리 $K$가 공백으로 구분되어 주어진다. $(1 \le H \le 1000, 1 \le D \le 10, 1 \le K \le 3)$  세 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 냥냥펀치의 데미지 $R_i$가 주어진다. $(1 \le R_i \le 100)$ 
• 출력: 춘배가 가질 수 있는 최대 체력을 출력한다. 답이 $0$ 이하일 경우 $-1$을 출력한다. ``` 예제1

입력 4 100 3 3 20 100 20 20 출력 69

## 풀이
깜짝 놀라게 하기만 없다면 전형적인 쉬운 dp문제이다. 깜짝 놀라게 하기는 한 번만 사용할 수 있고 지금 턴에 적용되는 것이 아닌 다음 턴에 적용된다. 따라서 게임당 한 번만 적용하기 위해 dp를 2개 만들어 깜짝 놀라게 하기를 사용하면 한 dp에서 다른 dp로 옮겨주는 방식으로 풀었다. 또한 깜짝 놀라게 하기를 사용 후 다음턴에는 데미지가 안들어오므로 네발로 걷기가 항상 따라와야 한다.

## 어려웠던 점
코드가 복잡하여 최대한 이해하기 쉽게 짜려고 노력했는데 결국 더러워졌다.

## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int n, h, d, k;
vector<vector<pair<int,int>>> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> h >> d >> k;
    dp = vector<vector<pair<int,int>>>(n+2);
    dp[0] = ;
    dp[1] = vector<pair<int,int>>(2);

    for(int i = 1; i < n+1; i++){
        int t;
        cin >> t;

        dp[i+1] = vector<pair<int,int>>(i+2);
        //웅크리기
        for(int j = 0; j < i; j++){
            int dist = d+j*k;
            int damage = max(0, t-dist);
            dp[i][j].first = max(dp[i][j].first, dp[i-1][j].first-damage/2);
            dp[i][j].second = max(dp[i][j].second, dp[i-1][j].second-damage/2);
            dp[i+1][j+1].second = max(dp[i+1][j+1].second, dp[i-1][j].first-damage);
            damage = max(0, damage-k);
            dp[i][j+1].first = max(dp[i][j+1].first, dp[i-1][j].first-damage);
            dp[i][j+1].second = max(dp[i][j+1].second, dp[i-1][j].second-damage);
        }
    }
    int overall_max = 0;
    for (auto &p : dp[n]) {
        overall_max = max({overall_max, p.first, p.second});
    }
    if(overall_max == 0) overall_max = -1;
    cout << overall_max;

    return 0;
}