백준 7579 - 앱

Java

7579 번 - 앱

문제

• 현재 활성화 되어있는 N개의 앱에 따라 메모리 바이트, 비용이 각각 주어진다.
• M 바이트 이상의 메모리를 추가로 확보해야 한다.
• 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

접근 방법

구하려는 문제는, 최소의 비용으로 M 바이트를 확보하는 것이다.
이를 반대로 생각하면, 최대의 비용으로 (전체 바이트 - M 바이트)를 구하면, 최소의 비용의 M바이트를 확보할 수 있다.

따라서, 전형적인 Knapsack Problem로 (전체 바이트 - M 바이트)를 N개의 메모리로 채우며 그 때의 최대 비용을 구하면 된다.
전체 비용에서 구한 최대 비용을 차감하면, 문제에서 원하는 최소 비용을 구할 수 있게 된다.

하지만, 문제의 조건에서의 N과 M이 다음과 같이 [1 ≤ M ≤ 10,000,000] [1 ≤ N ≤ 100] 범위가 크므로, 단순히 2차원 dp 배열로 해결하려 하면 메모리 초과가 난다.

따라서, 1차원 배열 2개만 설정하고, 서로의 값을 비교하며 KnapSack Problem을 해결하였다.

코드

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

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	int[] weight = new int[n + 1];
    	int[] cost = new int[n + 1];
    	
    	int wSum = 0, cSum = 0;
    	
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 1; i <= n; i++) {
    		weight[i] = stoi(stk.nextToken());
    		wSum += weight[i];		// 총 무게를 구한다.
    	}
    	
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 1; i <= n; i++) {
    		cost[i] = stoi(stk.nextToken());
    		cSum += cost[i];		// 총 비용을 구한다.
    	}
    	
    	int[][] dp = new int[2][wSum - m + 1];
    	
    	boolean flag = true;		// 서로 왕복하는 지점을 앙려주는 배열
    	int dp1 = 0, dp2 = 0;
    	for(int i = 1; i <= n; i++) {
    		if(flag) {
    			dp1 = 1;
    			dp2 = 0;
    		}
    		else {
    			dp1 = 0;
    			dp2 = 1;
    		}
    		// 1부터 전체 메모리 - M까지 탐색
    		for(int j = 1; j <= wSum - m; j++) {
    			if(j >= weight[i]) {	// 가방에 넣을 수 있으면
    				dp[dp1][j] = Math.max(dp[dp2][j], dp[dp2][j - weight[i]] + cost[i]);
    			}
    			else {
    				dp[dp1][j] = dp[dp2][j];
    			}
    		}
    		flag = !flag;	// 방향을 바꾼다.  
    	}
    	System.out.println(cSum - dp[dp1][wSum - m]);
    	
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

같은 스터디 그룹원의 풀이를 듣고 다시 풀어본 문제.
배낭 문제는 조금만 응용이 되어도 헤메는 것 같다.

개선할 점

정석 풀이도 확인해야 한다.