이번에 풀어본 문제는
백준 14728번 벼락치기 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N, T;
    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());
        T = Integer.parseInt(st.nextToken());

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

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= T; j++) {
                dp[i][j] = dp[i-1][j];
                if ((j - k) >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - k] + s);
                }
            }
        }

        System.out.print(dp[N][T]);
    }
}

📝 풀이

공부할 수 있는 시간이 T로 주어질 때, 가장 최대로 받을 수 있는 점수를 출력하는 문제입니다.
배낭 유형의 문제로, 앞선 유형들과 마찬가지로 이전 입력 (k, s)에서 갱신한 값을 우선 담아주고, 현재 값이 더 크다면 갱신해주는 순서로 흘러갑니다.
dp[i][j] 에서 i는 입력 행인 N, j는 소요한 시간이라고 생각하면 될 것 같습니다.
최종적으로 dp[N][T]를 출력하면 해결할 수 있습니다.

📜 후기

어제 이해하는데 시간이 조금 걸렸었기 때문에 배낭문제를 다시한번 풀어보았습니다. 오늘은 10분도 안돼서 풀어낸걸 보니 제대로 이해한게 맞는 것 같아요! 잊을 때 쯤 다시한번 풀어볼 생각입니다.