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() {
}
}