https://www.acmicpc.net/problem/7579
7579번: 앱
입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활
www.acmicpc.net
코드설명
DP(Dynamic Programming) + 배낭문제(냅색, KnapSack) 를 활용하는 문제입니다.
문제에서 dp를 사용한 방법은
dp[i][j] = K , 1차원에는 각 레벨이 주어지고, 2차원에는 각 금액별을 의미하며, K는 가지고 올 수 잇는 최대 메모리를 의마합니다.
위의 DP를 활용하여 해결할 수 있습니다. 처음에는 dp[j]로 진행하여 각 레벨별로 DP가 저장되지 않아 올바르게 진행되지 않았습니다.
처음에 재귀함수를 만들때 메모리를 기준으로 하여 가장 빠르게 최소값으로 원하는 메모리가 나오도록 설정하려고하였지만, 메모리초과로 실패했습니다. 문제에서 N은 100까지이고, 메모리는 10,000,000 이기에 dp[100][10000000] 이라면 4GB가 넘어갑니다. 그렇기에 금액기준으로 메모리를 낮추고, while문으로 모든 금액별로 구할 수 있습니다.
재귀함수에 대해 더 설명해보자면, simulate 함수는 현재 레벨과 현재 예산에 대한 최대 메모리를 계산합니다.
dp 배열을 활용하여 이미 계산된 값이 있다면 그 값을 반환하고, 없다면 계산을 수행합니다.
재귀적으로 현재 레벨에서 메모리를 구매하는 경우(temp1)와 구매하지 않는 경우(temp2) 중에서 최대 값을 선택하여 반환합니다. 결과값은 dp 배열에 저장되고, 이를 통해 중복 계산을 피합니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int N, M, K; public static int answer; public static int[] arr, memory, cost; public 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()); memory = new int[N]; cost = new int[N]; dp = new int[101][100 * 101]; //1차원에는 각 레벨이 주어지고, 2차원에는 각 금액별이며 최종적으로 DP는 가지고 올 수 잇는 최대 메모리를 의마합니다. for(int i=0;i<101;i++) { Arrays.fill(dp[i], -1); } st = new StringTokenizer(br.readLine()); for(int i=0;i<N;i++) { memory[i] = Integer.parseInt(st.nextToken()); } st = new StringTokenizer(br.readLine()); for(int i=0;i<N;i++) { cost[i] = Integer.parseInt(st.nextToken()); } int curCost = 0; while(true) { int result = simulate(0, curCost); //curCost로 가질 수 있는 최대 메모리를 구합니다. if(result >= M) { System.out.println(curCost); return ; } curCost++; } } public static int simulate(int level, int currentCost) { if(dp[level][currentCost] >= 0) return dp[level][currentCost]; if(level == N) return 0; int temp1=0, temp2=0; if(currentCost - cost[level] >= 0) temp1 = memory[level] + simulate(level + 1, currentCost - cost[level]); temp2 = simulate(level + 1, currentCost); return dp[level][currentCost] = Math.max(temp1, temp2); } }
메모리초과가 발생합니다.
이유는, 최대 메모리 값이 10,000,000 = (1천만) 의 값이 N이 100개이므로 1,000,000,000 = 10억 의 공간이 필요합니다.
문제에서 주어진 메모리 제한은 128MB 입니다..
int 형은 저장할떄 4 byte 씩 차지하므로, 10억 bit * 4 = 40 억 bit 이고,
40억 bit를 MB로 표현해보면, 40 억 bit / 8 bit = 5억 bit 입니다.
MB로 변환하면, 5억 bit / 1,000,000(백만) = 5,000MB 이므로 메모리 초과가 발생합니다.
그렇다면 메모리 초과를 어떻게 피할 수 있을까요? 비용 단위로 simulate 를 실현합니다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int N, M; public static Memory[] memoryArr; public static int[][] dp; // 각 메모리 별로 앱 비활성화 비용을 DP에 저장합니다. public static int MAX = 10000000 + 1; //필요한 메모리 M 바이트의 최대값인 10,000,000 을 선언합니다. 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()); memoryArr = new Memory[N]; dp = new int[N][MAX]; answer = MAX; st = new StringTokenizer(br.readLine()); for(int i=0;i<N;i++) { int inputMemory = Integer.parseInt(st.nextToken()); memoryArr[i] = new Memory(); memoryArr[i].memory = inputMemory; Arrays.fill(dp[i], -1); } st = new StringTokenizer(br.readLine()); for(int i=0;i<N;i++) { int inputCost = Integer.parseInt(st.nextToken()); memoryArr[i].cost = inputCost; } answer = simulate(0, M); System.out.println(answer); } public static int simulate(int level, int memory) { if(memory <= 0) { //만약 memory 가 0 보다 작거나 같아진다면 해당 방법은 성공입니다. return 0; } if(level >= N) { //N개의 앱을 모두 비활성화한 경우에도 안된경우에는 최대값을 반환하여 해당 방법은 불가하다는 것을 알려줍니다. return MAX; } if(dp[level][memory] != -1) return dp[level][memory]; //최소의 비용을 구하는 것이 목적이다. int resultA = MAX, resultB = MAX; resultA = memoryArr[level].cost + simulate(level + 1, memory - memoryArr[level].memory); resultB = simulate(level + 1, memory); return dp[level][memory] = Math.min(resultA, resultB); } } class Memory{ int memory; int cost; public Memory() { } }
비용단위로 최대 메모리양을 검색합니다.
본인이 원하는 메모리양을 가장 먼저 충족하는 경우가 최소비용이 될 것 입니다.
아래의 코드에서 보면, 의문이 드는점은, 각 simulate(0, cost)를 진행할때마다 왜 DP를 다시 초기화되지 않는지 궁금증이 생깁니다.
이유는, 이미 이전에 해당 비용에서의 메모리 최대값을 계산하였기 떄문입니다.
이를 통해, 앞서 계산했던 부분들에 대해 반복적인 연산을 진행하지 않습니다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int N, M; public static Memory[] memoryArr; public static int[][] dp; // 각 비용별로 최대 메모리 사용량을 DP에 저장합니다. // 최대 100개의 앱의 비용이 100개이므로, 100 * 100 + 1 로 처리합니다. public static int MAX = 100 * 100 + 1; 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()); memoryArr = new Memory[N]; dp = new int[N][MAX]; answer = MAX; st = new StringTokenizer(br.readLine()); for(int i=0;i<N;i++) { int inputMemory = Integer.parseInt(st.nextToken()); memoryArr[i] = new Memory(); memoryArr[i].memory = inputMemory; Arrays.fill(dp[i], -1); } st = new StringTokenizer(br.readLine()); for(int i=0;i<N;i++) { int inputCost = Integer.parseInt(st.nextToken()); memoryArr[i].cost = inputCost; } for(int i=0; i<100*100 + 1; i++) { int maxMemoryAtCost = simulate(0, i); if(maxMemoryAtCost >= M) { answer = i; break; } } System.out.println(answer); } public static int simulate(int level, int cost) { if(level >= N) { return 0; } if(dp[level][cost] != -1) return dp[level][cost]; int resultA = 0, resultB = 0; if(cost - memoryArr[level].cost >= 0) resultA = memoryArr[level].memory + simulate(level + 1, cost - memoryArr[level].cost); resultB = simulate(level + 1, cost); return dp[level][cost] = Math.max(resultA, resultB); } } class Memory{ int memory; int cost; public Memory() { } }