[백준] 14725 : 벼락치기 - Java

• 백준 문제 URL

---

문제 요약

시험까지 남은 총 공부 시간 T가 주어지고,
각 단원마다 공부에 필요한 시간(K) 과 얻을 수 있는 점수(S) 가 주어진다.

공부할 수 있는 시간의 총합이 T를 넘지 않도록 단원들을 선택했을 때,
얻을 수 있는 최대 점수를 구하는 문제다.

즉, 이 문제는 전형적인 0-1 배낭 문제(Knapsack) 형태이며,
각 단원은 한 번만 선택할 수 있다.

---

핵심 아이디어

이 문제는 "단원"을 "물건"으로, "공부 시간"을 "무게"로 치환한 형태의 Knapsack 응용이다.

• 단원 i: time = 공부 소요 시간, score = 단원 점수
• 제한 무게: T (총 공부 가능 시간)

각 시간마다 “그 시점까지의 최대 점수”를 저장하며,
매 단원마다 뒤에서부터 dp 갱신(0-1 Knapsack 방식)을 반복한다.

평범한 배낭 문제와 완벽하게 일치하는 문제

---

DP 정의 & 점화식

dp 정의

• dp[i]: i시간 동안 공부했을 때 얻을 수 있는 최대 점수

---

초기값

• dp[0] = 0 (시간이 0이면 아무 공부도 못 하므로 점수도 0)

---

점화식

각 단원에 대해,
현재 공부 시간 time, 점수 score를 가지고,
현재 제한 시간부터 거꾸로 갱신한다.

dp[j] = max(dp[j], dp[j - time] + score)
단, j >= time일 때만 가능.

이렇게 뒤에서부터 갱신해야
한 단원을 여러 번 선택하는 것을 방지할 수 있다.

---

최종 답

• dp[t] = 최대 공부시간 t 안에서 얻을 수 있는 최대 점수

---

전체 코드 (제출용)

package A5DP.Baekjoon;

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

public class G14728벼락치기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 단원 개수
        int t = Integer.parseInt(st.nextToken()); // 총 공부 가능 시간

        int[][] timeWithScore = new int[n][2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            timeWithScore[i][0] = Integer.parseInt(st.nextToken()); // 공부 시간
            timeWithScore[i][1] = Integer.parseInt(st.nextToken()); // 점수
        }

        int[] dp = new int[t + 1];
        for (int i = 0; i < n; i++) {
            int time = timeWithScore[i][0];
            int score = timeWithScore[i][1];

            for (int j = t; j >= time; j--) {
                dp[j] = Math.max(dp[j], dp[j - time] + score);
            }
        }

        System.out.println(dp[t]);
    }
}

---

예제 시뮬레이션

예를 들어,
T = 7, 단원이 다음과 같이 주어진 경우를 보자.

단원	필요 시간(K)	점수(S)
1	2	4
2	4	7
3	3	5

• 7시간 안에서 얻을 수 있는 최대 점수는 12점
  (단원 1 + 단원 3 조합)

---

핵심 포인트 정리

• 전형적인 0-1 배낭 구조이므로, 역순 갱신 for문 구조를 그대로 사용.
• 각 단원을 ‘딱 한 번만’ 선택해야 하므로 역순(for j = t → time)으로 순회.
• dp 배열 하나로 메모리 최적화 (1차원 Rolling DP).
• 계산 결과 dp[t]가 곧 답.