[BOJ/Java] 1535: 안녕

문제

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

총 N명의 사람이 있다.

사람과 악수를 하게 되면, 체력은 잃고 기쁨을 얻는다.

체력은 100이며, 체력이 0이나 음수가 되지 않으면서 얻을 수 있는 최대의 기쁨을 구해야 한다.

 

 풀이

문제 자체는 0-1 배낭 문제와 같다. 하지만 평범한 배낭(https://www.acmicpc.net/problem/12865)보다는 인풋 값이 작아 다른 알고리즘을 시도해도 괜찮다.

 

알고리즘은 다음과 같다.

1. cost[i]는 i번째 사람에게 잃는 체력, value[i]는 i번째 사람에게 얻을 수 있는 기쁨이다.
2. dp[i][j]는 i번째 사람까지 고려했을 때, 체력을 j만큼 썼을 때의 최대 기쁨이다.
3. 현재 사람과 악수할 수 없는 경우(현재 체력보다 잃는 체력이 크거나 같은 경우), 이전 값을 선택한다. (dp[i][j] = dp[i-1][j]) (체력이 0이나 음수가 되기 때문이다.)
4. 현재 사람과 악수할 수 있는 경우, 이전 값과 현재 사람과 악수해서 얻을 수 있는 기쁨을 비교해서 더 큰 값을 선택한다. (max(dp[i-1][j], dp[i-1][j - cost[i]] + value[i])

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        int[] cost = new int[n+1];
        int[] value = new int[n+1];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            cost[i] = Integer.parseInt(st1.nextToken());
            value[i] = Integer.parseInt(st2.nextToken());
        }

        int health = 100;
        int[][] dp = new int[n+1][health+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= health; j++) {
                if (cost[i] >= j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - cost[i]] + value[i]);
                }
            }
        }

        System.out.println(dp[n][health]);
    }

}