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

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

 

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

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

---

1.  아이디어

 

0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.

챕터의 종류가 최대 20가지여서 부분집합을 활용해서도 해결할 수 있었다.

---

2. 문제풀이

 

부분집합은 재귀를 통한 완전탐색으로 진행하되 N일이 넘어가는 집합은 더 탐색하지 않도록 백트래킹을 했다.

다이나믹 프로그래밍은 날짜를 인덱스 값을 페이지 수로 하는 일반적인 0-1 배낭으로 해결할 수 있었다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main_PowerSet {

    private static class Item {
        int day;
        int page;

        public Item(int day, int page) {
            this.day = day;
            this.page = page;
        }
    }

    private static int N;
    private static int M;
    private static Item[] items;
    private static int ans = 0;

    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());

        items = new Item[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int page = Integer.parseInt(st.nextToken());
            items[i] = new Item(day, page);
        }

        powerSet(0, 0, 0);

        System.out.println(ans);
    }

    private static void powerSet(int selIdx, int day, int page) {
        if (day > N) return;

        if (selIdx == M) {
            ans = Math.max(ans, page);
            return;
        }

        powerSet(selIdx + 1, day, page);
        powerSet(selIdx + 1, day + items[selIdx].day, page + items[selIdx].page);
    }

}

import java.io.*;
import java.util.*;

public class Main_DP_1D {

    private static class Item {
        int day;
        int page;

        public Item(int day, int page) {
            this.day = day;
            this.page = page;
        }
    }

    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 M = Integer.parseInt(st.nextToken());

        Item[] items = new Item[1 + M];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int page = Integer.parseInt(st.nextToken());
            items[i] = new Item(day, page);
        }

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

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

import java.io.*;
import java.util.*;

public class Main_DP_2D {

    private static class Item {
        int day;
        int page;

        public Item(int day, int page) {
            this.day = day;
            this.page = page;
        }
    }

    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 M = Integer.parseInt(st.nextToken());

        Item[] items = new Item[1 + M];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int page = Integer.parseInt(st.nextToken());
            items[i] = new Item(day, page);
        }

        int[][] dp = new int[1 + M][1 + N];
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (j < items[i].day) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i].day] + items[i].page);
            }
        }

        System.out.println(dp[M][N]);
    }
}

---

4. 후기

 

- 부분집합

- 1차원 dp

- 2차원 dp