[BOJ/JAVA] 1535번: 안녕

1535번: 안녕

1535번: 안녕

키워드

세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다.

**주어진 체력내**에서 **최대한의 기쁨**을 느끼는 것이다.

세준이의 **체력은 100이고, 기쁨은 0**이다.

세준이의 체력이 **0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것**이 된다.

---

구현

index번 사람에게 인사를 할 것인지를 선택한다.

만약 인사를 할 때 현재 체력보다 깎이는 체력이 많다면 인사를 하지 않는다.

---

코드

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

public class java_1535 {
    static int N;

    static int happyList[];
    static int hitList[];

    static int cache[][];

    static int dp(int index, int hitPoint) {
        if (index >= N) {
            return 0;
        }

        if (cache[index][hitPoint] != -1) {
            return cache[index][hitPoint];
        }

        cache[index][hitPoint] = 0;
        // 이번 인덱스를 선택한다.
        if (hitPoint - hitList[index] > 0) {
            cache[index][hitPoint] = Math.max(cache[index][hitPoint],
                    dp(index + 1, hitPoint - hitList[index]) + happyList[index]);
        }
        // 건너 뛴다.
        cache[index][hitPoint] = Math.max(cache[index][hitPoint], dp(index + 1, hitPoint));

        return cache[index][hitPoint];
    }

    static int solve() {
        int result = 0;

        cache = new int[N][101];
        for (int i = 0; i < N; i++) {
            Arrays.fill(cache[i], -1);
        }

        result = dp(0, 100);

        return result;
    }

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

        N = Integer.parseInt(br.readLine());

        happyList = new int[N];
        hitList = new int[N];

        // 잃는 체력
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            hitList[i] = Integer.parseInt(st.nextToken());
        }

        // 기쁨
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            happyList[i] = Integer.parseInt(st.nextToken());
        }

        int result = solve();

        System.out.println(result);

        br.close();

    }
}

---