[백준] 16493 최대 페이지 수 - Java

 

 

 

문제 출저

https://www.acmicpc.net/problem/16493

16493번: 최대 페이지 수

 

 

 

문제 풀이

남은 일수와 챕터 수가 주어집니다. 챕터는 필요한 공부 일수와 읽게 되는 페이지 수로 구성되어 있습니다. 남은 일수 동안 챕터를 읽어서 가장 많이 읽는 페이지 수를 구해야 합니다. 

 

배낭 알고리즘을 적용하여 문제를 풀었습니다.

이차원 int 배열 dp를 사용합니다. int[][] dp = new int[m+1][n+1]

m : 챕터 수, n : 남은 날짜 수 

챕터를 하나씩 비교합니다. 전에 챕터와 현재 챕터를 선택했을 때 더 큰 것을 dp에 저장하는 식으로 메모리제이션 합니다. 

점화식 : dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-day] + page)

 

이런 식으로 dp를 채우면 dp[m][n]에 정답이 저장되게 됩니다. 

 

 

 

소스코드

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

/*
최대 페이지 수
https://www.acmicpc.net/problem/16493
 */

public class Main {

    static int n; // 남은 날 수
    static int 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());
        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 page = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= day) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-day] + page);
                }
            }
        }

        System.out.println(dp[m][n]);

    }

}