https://www.acmicpc.net/problem/16493
16493번: 최대 페이지 수
첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이
www.acmicpc.net
코드설명
배낭문제(냅색, KnapSack) + DP(Dynamic Programming) 문제입니다.
먼저 문제를 보자마자, 완전탐색이라는 것은 알 수 있습니다.
이유는 시간복잡도를 계산해보면 2^20 이 최악의 경우입니다. 2^20 = 1,048,576 이므로 거뜬히 작동합니다.
이곳에 메모이제이션까지 적용하면 더 줄일 수 있습니다.
Top - Down 방식으로 진행하였고, 냅색의 전형적인 문제이므로 냅색의 로직을 적용하면 해결할 수 있습니다.
문제에서 생각을 잘못햇었던 부분은, 아래 부분입니다.
if(day - book[level].day >= 0) {
현재 날짜에서 다음 책을 읽었을떄 딱 0일이 되도록 읽으면 해당 책을 읽을 수 있습니다.
처음에는 > 0 로 생각하여(즉, 날짜가 반드시 0일보다 커야한다) 처리하여 틀렸었습니다.
이 문제에서 왜 아래와 같이 인자 2개 level, day만을 활용하여 진행할까 라는 궁금증이 생길 수 있습니다.
public static int simulate(int level, int day) {이유는, 메모리제이션을 사용하기 위해서입니다.
메모리제이션은 동일한 계산을 반복하지 않도록 이미 계산된 값을 재사용하는 기법입니다.
이를 위해서는 함수가 '참조 투명' 즉, 동일한 인자에 대해 항상 동일한 결과를 반환해야 합니다.
그러나, 만약 simulate(int level, int day, int page) 로 진행할경우 '참조 투명' 하지 않습니다.
왜냐하면 같은 level과 people에 대해 cost값이 다르게 적용될 수 있기 때문입니다.
예를 들어, simulate(1, 100, 0) 을 호출하는 경우
1. 현재 책을 읽는 경우 simulate(2, 100 - 2, 0 + 10)
2. 현재 책을 읽지않는 경우 simulate(2, 100 - 0, 0 + 0)
이렇게 두가지로 나뉘게 됩니다.
이 경우, simulate(1, 100, 0) 이라는 함수호출에 대해 다른 출력비용이 나오게 됩니다.
따라서 이 함수는 '참조 투명'하지 않으므로 메모리제이션을 적용할 수 없습니다.
정리해보자면, 메모리제이션을 적용하려면 같은 상태에 대해 항상 같은결과를 반환하는 함수가 필요합니다. 즉, 같은 인자에 대해 항상 같은 결과를 반환해야합니다.
또, 캐싱을 활용하여 중복 계산을 피합니다. 이 문제에서는 같은 depth에 같은 날짜로 들어왔을때 다시 중복된 계산을 하지 않도록 아래처럼 Cache 배열을 활용하여 중복계산을 피합니다.
static int[][] cache = new int[21][201];코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M, H, T;
public static int answer = 0;
public static int[] arr;
public static int[] days, page;
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());
days = new int[M];
page = new int[M];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
days[i] = Integer.parseInt(st.nextToken());
page[i] = Integer.parseInt(st.nextToken());
}
System.out.println(simulate(0, 0));
}
public static int simulate(int level, int curDay) {
if(level == M) return 0;
if(curDay > N) return 0;
int temp1 = 0;
if(curDay + days[level] <= N)
temp1 = page[level] + simulate(level + 1, curDay + days[level]);
int temp2 = 0 + simulate(level + 1, curDay + 0);
return Math.max(temp1, temp2);
}
}
다르게 풀어본코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static Book[] book;
public static int answer = 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());
book = new Book[M];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int inputDay = Integer.parseInt(st.nextToken());
int inputPageSize = Integer.parseInt(st.nextToken());
book[i] = new Book(inputDay, inputPageSize);
}
answer = simulate(0, N);
System.out.println(answer);
}
public static int simulate(int level, int day) {
if(level >= M) {
return 0;
}
int resultA = 0, resultB = 0;
if(day - book[level].day >= 0) {
resultA = book[level].pageSize + simulate(level + 1, day - book[level].day);
}
resultB = simulate(level + 1, day);
return Math.max(resultA, resultB);
}
}
class Book{
int day;
int pageSize;
public Book() {
}
public Book(int day, int pageSize) {
this.day = day;
this.pageSize = pageSize;
}
}
DP를 활용하여 시간을 줄여봅니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static Book[] book;
public static int[][] DP;
public static int answer = 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());
book = new Book[M];
DP = new int[M+1][201];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int inputDay = Integer.parseInt(st.nextToken());
int inputPageSize = Integer.parseInt(st.nextToken());
book[i] = new Book(inputDay, inputPageSize);
}
answer = simulate(0, N);
System.out.println(answer);
}
public static int simulate(int level, int day) {
if(DP[level][day] > 0) {
return DP[level][day];
}
if(level >= M) {
return 0;
}
int resultA = 0, resultB = 0;
if(day - book[level].day >= 0) { //책을 읽은 후 0일 이상이 남아있다면, 가능하다.
resultA = book[level].pageSize + simulate(level + 1, day - book[level].day);
}
resultB = simulate(level + 1, day);
return DP[level][day] = Math.max(resultA, resultB);
}
}
class Book{
int day;
int pageSize;
public Book() {
}
public Book(int day, int pageSize) {
this.day = day;
this.pageSize = pageSize;
}
}
재귀 + 메모이제이션을 활용합니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, P, K, A, B, X, R, T, S, C;
static long answer = 0;
static int[][] arr = new int[21][2];
static int[][] cache = new int[21][201];
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());
for(int i=0;i<21; i++)
Arrays.fill(cache[i], -1);
// 2^20 시간복잡도 ? = 2^16 = 65536 12만 24만 48만 69만
for(int i=0;i<M; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
answer = DFS(0, N);
System.out.println(answer);
}
static int DFS(int depth, int days) {
if(depth == M) return 0;
if(cache[depth][days] != -1) return cache[depth][days];
int ret = 0;
ret = DFS(depth + 1, days);
if(days - arr[depth][0] >= 0) {
ret = Math.max(ret, DFS(depth + 1, days - arr[depth][0]) + arr[depth][1]);
}
return cache[depth][days] = ret;
}
}