[Java] 1535 안녕

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

주어진 체력이 100 일 때 최대 기쁨을 구해야하므로, dp 사용
1. dp[현재사람][체력] == dp[N+1][100] 으로 생성
2. (dp[현재사람-1][현재체력-현재사람체력] + 현재사람기쁨) 으로 체력당 최댓값을 구할 수 있다!

💡 백준 예시 1번을 통한 이해

1. dp[1][0]~ dp[1][100]
dp[1] :첫번째 사람일 때, 따라서
dp[1][0] 첫번째 사람일 때 체력 0일 때, dp[1][100]첫번째 사람일 때 체력 100일 때
: 첫번째 사람일 때 체력 100까지의 최댓값은 20

2. dp[2][0]~dp[2][100]
두번째 사람의 체력소모는 21, 기쁨은 30 이므로,
두번째 사람 체력 21일 때 즉 dp[2][21] = 30 이 된다.

dp[2][1]~dp[2][20] : 두번째 사람의 값이 없으므로, dp[1][현재체력]에서 가져온다
dp[2][21] = 30
dp[2][22] ~ dp[2][100] : 현재 첫번째 사람 체력소모 1, 두번째 사람 체력소모 21 로 총 체력소모는 22이다.
따라서 dp[2][22] = 첫번째 사람 기쁨 + 두번째 사람 기쁨 이 된다 = 50
dp[2][23]~dp[2][100] 은 dp[2][22]의 최댓값을 계속 가져온다.

3. dp[3][0]~dp[3][100]
세번째 사람의 체력소모는 79, 기쁨은 25이므로,
dp[3][79] = 25 가 되어야 하지만?
dp[2][79] 즉 1,2번 사람의 기쁨을 계산했을 때 50 이므로,Math.max를 통하여 50 이란 결과를 도출한다.

이렇게 계산을 통해 dp를 출력하게 되면 아래와 같은 결과가 나오는 걸 볼 수 있다.

아이고 너무 길어서 2개로 나누었다

따라서 점화식은
dp[i][j] = Math.max(dp[i-1]j-HealthArr[i]]+HappyArr[i], dp[i-1][j]);

3. 코드

import java.awt.Point;
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int N;
    static int[] HealthArr, HappyArr;
	static int[][] dp;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
		HealthArr = new int[N+1];
		HappyArr = new int[N+1];
		dp = new int[N+1][100];

		StringTokenizer Healthst = new StringTokenizer(br.readLine());
		StringTokenizer Happyst = new StringTokenizer(br.readLine());
		for (int i = 1; i < N+1; i++) {
			HealthArr[i] = Integer.parseInt(Healthst.nextToken());
			HappyArr[i] = Integer.parseInt(Happyst.nextToken());
        }

		for(int i=1;i<N+1;i++){
			for(int j=0;j<100;j++){
				if(j >= HealthArr[i]){
					dp[i][j] = Math.max(dp[i-1][j-HealthArr[i]]+HappyArr[i], dp[i-1][j]);
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		System.out.println(dp[N][99]);
    }
}