[백준 1535] 안녕

 

문제풀이 

이 문제는 배낭문제 대표 유형이다.

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

만약, 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨도 못느낀다. 즉, 이때의 기쁨은 0이다.

세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

 

최대 기쁨을 구하기 위해 dp[][]를 사용한다. dp[n][j]의 의미는 현재 세준이의 체력이 j이고 n번째 사람까지 고려했을때 얻을 수 있는 최대의 기쁨이다.

 

문제를 풀면서 상황은 두가지로 나눌 수 있다.

• 인사를 할 수 없는 경우(현재 세준이의 체력보다 n번째 사람에게 인사할 때 드는 체력이 더 큰 경우)
• 인사를 할 수 있는 경우
  • 인사를 하는 것이 최대의 기쁨인지, 인사를 하지 않는 것이 최대의 기쁨인지 구분해 줄 필요가 있다.

 

인사를 할 수 없는 경우는 (j - n번째 사람에게 인사할 때 필요한 체력 < 1) 인 경우를 고려해주어야 한다. 만약 뺄셈의 결과가 음수이거나 0이라면 기쁨을 얻을 수 없으므로 0이다. 즉, n-1번째 사람까지 고려했을때 얻을 수 있는 최대의 기쁨과 동일하다.

 

인사를 할 수 있는 경우는 인사를 하지 않는 경우인 dp[n-1][j]인 경우와 인사를 하는 경우인 n번째 사람에게 인사하여 얻는 기쁨 + dp[n-1][j - n번째 사람에게 인사할 때 필요한 체력] 중에서 큰 값을 선택해야 한다.

 

※ 참고로 배낭문제는 물건을 여러번 쓸 수 있는 지 쓸 수 없는 지에 대해서 나뉜다. 이번 문제에서는 여러번 쓸 수 없으므로 인사를 할 수 있는 경우를 고려할 때, curJ + dp[n-1][j-curL] 부분에서 dp[n]이 아닌 dp[n-1]이다.

 

구현

import java.io.*;
import java.util.*;

public class Solution_for_1535 {
    static int N;
    static int[] L; // 체력
    static int[] J; // 기쁨

    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());

        L = new int[N+1];
        J = new int[N+1];

        dp = new int[N+1][101];

        st = new StringTokenizer(br.readLine());
        for (int n = 1; n < N+1; n++) {
            L[n] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int n = 1; n < N+1; n++) {
            J[n] = Integer.parseInt(st.nextToken());
        }

        // dp[i][j] = i번째 사람까지 고려했을 때, 체력이 j라면 얻을 수 있는 최대 기쁨
        for (int j = 1; j < 101; j++) {
            for (int n = 1; n < N+1; n++) {
                int curL = L[n];    // 체력
                int curJ = J[n];    // 기쁨

                // 안 만나는 경우
                if (j - curL < 1) {
                    dp[n][j] = dp[n-1][j];
                }
                // 만날 수 있는 경우
                else {
                    dp[n][j] = Math.max(dp[n-1][j], curJ + dp[n-1][j-curL]);
                }
            }
        }

        System.out.println(dp[N][100]);
    }
}