[Java] 백준 7579번: 앱

[문제 바로 가기] - 앱

📌 유형 : DP (배낭)

💡 아이디어

평범한 배낭 문제와 비슷하다고 생각하여 처음엔 dp 배열을 각 메모리 값에 따른 최소 비용 값을 구하려고 하였지만, 시간초과 위험이 있어 다른 풀이로 바꾸었다.

dp 배열을 [앱][비용] = 최대 메모리 크기로 저장해가며 메모리 크기가 M보다 클 경우의 최소 비용을 구했다. 이때 들 수 있는 최대 비용은 모든 비용의 합까지 가능하므로 costSum까지로 범위를 설정해주었다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] memory = new int[N + 1];
		int[] cost = new int[N + 1];
		
		// 차지하는 메모리 저장
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			memory[i] = Integer.parseInt(st.nextToken());
		}
		
		int costSum = 0;
		
		// 비용 저장
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			cost[i] = Integer.parseInt(st.nextToken());
			costSum += cost[i];
		}
		
		int[][] dp = new int[N + 1][costSum + 1];
		
		int answer = Integer.MAX_VALUE;
		
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= costSum; j++) {
				if (i == 0) {
					if (j >= cost[i]) dp[i][j] = memory[i];
				} else {
					if (j >= cost[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);
					else dp[i][j] = dp[i - 1][j];
				}
				
				if (dp[i][j] >= M) answer = Math.min(answer, j);
			}
			
			
		}
		
		System.out.println(answer);
	}
}