이번에 풀어본 문제는
백준 16493번 최대 페이지 수 입니다.

📕 문제 링크

❗️코드

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

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

        int [][] input = new int[M + 1][2];
        dp = new int[M + 1][N + 1];

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int pages = Integer.parseInt(st.nextToken());

            input[i][0] = day;
            input[i][1] = pages;
        }

        for (int i = 1; i <= M; i++) {
            int day = input[i][0];
            int pages = input[i][1];

            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i-1][j];
                if ((j - day) >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - day] + pages);
                }
            }
        }
        System.out.print(dp[M][N]);
    }
}

📝 풀이

남은 대출 기간동안 읽을 수 있는 최대 페이지 수를 구하는 문제입니다.
배낭 문제 유형으로, dp를 활용하여 해결할 수 있습니다.
dp[i][j] 에서 i는 챕터, j는 소요된 일 수를 의미합니다.
dp[i-1][j] 값으로 우선 초기화 시켜준 후, 앞서 채워진 최댓값 (dp[i-1][j-현재 소모할 일 수]) 과 이전 dp값을 비교해주며 갱신해주면 됩니다.
마지막으로 dp[M][N]을 출력해주면 해결할 수 있습니다.

📜 후기

dp 문제를 연습하다가 배낭 문제를 풀어보았는데, 오랜만이라 역시 어렵게 느껴졌습니다. 복습을 위해 내일도 풀어볼 생각입니다!