[알고리즘] 나비의 간식을 훔쳐먹은 춘배 성공

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

package baekjoon.solution30407;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main2 {

    static int N;
    static int H;
    static int D;
    static int K;
    static int[] R;

    static int[][][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        R = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            R[i] = Integer.parseInt(st.nextToken());
        }
        dp = new int[N][65][2][2];

        int ans = solve(0, D, 0, 0, H);
        System.out.println(ans);
    }

    static int solve(int turn, int distance, int usedSurprise, int nullify, int health) {
        if (health <= 0) {
            return -1;
        }

        if (turn == N) {
            return health;
        }

        if (dp[turn][distance][usedSurprise][nullify] >= health) {
            return -1;
        }
        dp[turn][distance][usedSurprise][nullify] = health;

        int maxHealth = -1;
        int res = -1;
        int remain_health = -1;

        int damage = 0;
        damage = Math.max((R[turn] - (distance + K)), 0);
        remain_health = health - damage;
        if (nullify == 1) {
            res = solve(turn + 1, distance + K, usedSurprise, 0, health);
        } else {
            res = solve(turn + 1, distance + K, usedSurprise, nullify, remain_health);
        }
        maxHealth = Math.max(maxHealth, res);

        damage = Math.max(((R[turn] - distance) / 2), 0);
        remain_health = health - damage;
        if (nullify == 1) {
            res = solve(turn + 1, distance, usedSurprise, 0, health);
        } else {
            res = solve(turn + 1, distance, usedSurprise, nullify, remain_health);
        }
        maxHealth = Math.max(maxHealth, res);

        if (usedSurprise == 0) {
            damage = Math.max(R[turn] - distance, 0);
            remain_health = health - damage;
            res = solve(turn + 1, distance, 1, 1, remain_health);
            maxHealth = Math.max(maxHealth, res);
        }

        return maxHealth;
    }
}

나의 풀이

- 재귀를 이용해서 탐색하는데 그 과정에서 dp를 이용해야 하는 문제였다.

-