[백준]14728: 벼락치기 - JAVA

[백준]14728: 벼락치기

14728번: 벼락치기

풀이

🪑 이러한 문제 유형은 배낭문제(knapsack)이라는 대표적인 DP유형이다. 배낭문제를 예에에전에 풀어본적은 있어서 이 문제가 DP라는건 언뜻 기억이 났지만 접근 방법이 기억 나지 않아 헤멨던 문제이다. 

 

DP라는 느낌이 들면 일단 그림을 그려보면서 이해해 보는 것이 가장 좋은 것 같다!

 

문제의 조건을 살펴보자. 배낭문제와 매핑해서 생각해 보자.

• 시험의 단원이 의미하는 바는 배낭문제의 물건 번호와 같다.
• 시험 단원 별 소요되는 시간은 배낭문제의 배낭에 담는 물건의 무게와 같다.
• 단원 문제의 배졈은 물건의 가치와 같다.
• 시험 단원의 개수는 배낭에 담을 수 있는 물건의 종류와 같다.
• 시험까지 총 공부할 수 있는 시간은 배낭이 담을 수 있는 최대 무게와 같다.

 

 

🔧 이제 문제를 풀어보자.

1. 단원 별 정보를 차례대로 입력 받는다.
2. 단원 별 정보를 가지고 탐색을 수행한다.
3. 배열의 마지막 인덱스에 있는 값을 출력한다.

 

🔹 단원 별 정보를 차례대로 입력 받는다.

- 단원 별로 주어지는 정보는 공부 시간과 배점이다. 해당 정보를 입력 받는다.

 

🔹 단원 별 정보를 가지고 DP를 수행한다.

- DP는 점화식을 세우는 것이 가장 중요하다. 공통의 문제를 찾아내어 점화식을 만들기 위해 표를 그리며 동작 과정을 이해해 보자.

 

📌 표를 이해해보자. 

 

- N은 각 단원별 정보를 의미한다. 첫 번째 인덱스는 공부하는데 소요되는 시간이 50시간이며 배점은 40점이라는 것을 의미한다.

- T는 시험까지 총 공부할 수 있는 시간을 의미한다.

- 배열에 저장되는 값은 얻을 수 있는 최대 배점을 의미한다.

 

🔎 첫 번째 단원(50시간-40점) 부터 탐색해 보자.

✔ 시간이 0시간 일때는 어떠한 단원도 공부할 수 없다. 그러므로 0을 채워넣는다.

 

✔ 시간이 50이 되면 현재 탐색하고 있는 단원인 첫 번째 단원을 공부할 수 있게 된다. 공부를 하면 40점의 배점을 얻을 수 있으므로 40을 채워 넣는다.

✔ 그 뒤로는 시간이 몇시간이 되어도 현재 탐색 단원이 첫 번째 단원 밖에 없으므로 40을 계속 채워 넣는다.

 

 

🔎 두 번째 단원(100시간-70점)을 탐색해 보자. 

✔ 50시간일때 획득할 수 있는 최대 점수는 첫 번째 단원을 공부한 40점과 동일하다.

✔ 100시간이 되는순간 두 번째 단원을 공부하고 70점을 획득할 수 있다.

 

✔ 150시간이 되는 순간을 잘 살펴보자.

✔ 동일 시간일 때 이전까지 계산했던 최대 점수는 40점이다. 이 점수를 기억해 두자.

✔ 만약 150시간일 때 더 추가해서 공부할 수 있는 단원이 존재 한다면 해당 배점을 더해줘야 한다. 위에 경우에서 150시간이 되는 순간 현재 단원만큼 공부한 시간을 뺀 50시간에서의 최대값인 40점을 현재 단원을 공부해서 얻을 수 있는 점수인 70점과 더해준 110점이 해당 된다.

✔ 구한 110점과 이전까지 계산했던 최대 점수인 40점 중에서 더 큰값을 선택하면 된다.

✔ 이후로는 더 공부할 수 있는 단원이 없으므로 최대 점수는 현재 까지의 최대 점수인 110점으로 동일하다.

 

🔎 세 번째 단원(200시간-150점)을 탐색해 보자.

✔ 우선 50시간, 150시간일 때의 최대값을 적어준다. 

✔ 200시간이 되었을 때 현재 시간의 최대 점수인 110점 보다 현재 단원을 공부해서 얻을 수 있는 점수인 150점이 더 크므로 150점을 적어준다.

 

✔ 250시간이 되었을때 3번째 단원에 첫 번째 단원을 추가로 공부할 수 있게 된다.

✔ 250시간까지의 현재까지 최대 얻을 수 있는 점수는 110점이다.

✔ 이때 현재 단원을 공부하는데 필요한 시간을 뺀 50시간일때 얻을 수 있는 점수 40점과 현재 단원을 공부해서 얻을 수 있는 150점을 더한 190점이 현재 추가로 공부해서 얻을 수 있는 최대 점수가 된다.

✔ 이 두 값(110, 190중에 더 큰 값인 190점을 적어준다.

 

이런 매커니즘으로 표를 채우면 다음과 같은 표가 완성된다.

✔ 이때 얻을 수 있는 최대 값은 맨 마지막 인덱스에 저장이 되는것을 알 수 있다.

 

 

📌 이제 점화식을 세워보자! 크게 아래와 같은 두 가지 경우가 존재한다.

 

🔹 현재 단원을 공부할 수 있는 시간인 경우 (N.시간 <= T)

• 현재 시간(T) 까지 얻을 수 있는 최대 점수는 이전 N의 현재 시간에서 얻을 수 있는 최대 점수와, 이전 N의 시간에서 현재 N의 시간을 뺐을 때의 최대 값에 현재 N의 점수를 더한 값이 된다.
• DP[N][T] = Math.max(DP[N - 1][T], DP[N - 1][T - N.T] + N.S) 

 

🔹 현재 단원을 공부할 수 없는 시간인 경우 (N.시간 > T)

• 현재 시간(T)까지 얻을 수 있는 최대 점수는 이전 N의 현재 시간에서 얻을 수 있는 최대 점수와 같다.
• DP[N][T] = DP[N - 1][T]

 

🔹 이제 식을 구해주었으므로 배열의 마지막 노드 값을 출력하면 된다. 

 

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int n = scan.nextInt();
        int t = scan.nextInt();
 
        Node[] node = new Node[n + 1]; 
        for(int i = 1; i <= n; i++) {
            int k = scan.nextInt();
            int s = scan.nextInt();
            node[i] = new Node(k, s);
        }
 
        int[][] dp = new int[n + 1][t + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= t; j++) {
                if(node[i].time <= j){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - node[i].time] + node[i].score);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n][t]);
    }
 
    public static class Node {
        int time;
        int score;
 
        public Node(int time, int score) {
            this.time = time;
            this.score = score;
        }
    }
}