[Java] 백준 7579 - 앱

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

 

 

---

풀이

얼핏 봐도 배낭 문제를 많이 닮아 있다

 

dp[i][w] = 최대 무게가 w인 배낭에서 i번째 물건까지 판단했을 때의 최대 가치

dp[i][m] = 최대 메모리가 m인 상태에서 i번째 앱까지 판단했을 때의 최대 비용

 

하지만 이렇게 하기에는 m이 최대 10,000,000까지 커져서 안됨

대신 기준점을 메모리가 아닌 비용으로 잡으면

 

dp[i][c] = 최대 비용이 c인 상태에서 i번째 앱까지 판단했을 때의 최대 메모리 사용량

 

여기서 c는 최대 100×100

위의 식을 이용해서 우리 원하는 메모리를 초과하는 비용의 최소를 구하면 끝!

---

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int appsCnt = Integer.parseInt(st.nextToken());
		int targetMemory = Integer.parseInt(st.nextToken());
		int[] memories = new int[appsCnt + 1];
		int[] costs = new int[appsCnt + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= appsCnt; i++) {
			memories[i] = Integer.parseInt(st.nextToken());
		}

		int costSum = 0;
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= appsCnt; i++) {
			costs[i] = Integer.parseInt(st.nextToken());
			costSum += costs[i];
		}

		int[][] dp = new int[appsCnt + 1][costSum + 1];
		int minCost = costSum;

		for (int i = 1; i <= appsCnt; i++) {
			for (int c = 0; c <= costSum; c++) {
				if (c - costs[i] >= 0) {
					dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - costs[i]] + memories[i]);
				} else {
					dp[i][c] = dp[i - 1][c];
				}

				if (dp[i][c] >= targetMemory) {
					minCost = Math.min(minCost, c);
				}
			}
		}

		System.out.println(minCost);
		br.close();
	}
}