[백준] 7579 - 앱

[문제링크]

7579번: 앱

 

0. 일반적인 냅색의 DP해결법을 적용하면 최대 100개의 물건에 대해 - 최대 10000000의 메모리를 고려해야 한다

  - 시간, 공간복잡도 둘 다 문제가 생긴다

  - 시간 복잡도 O(NM) = 10억

  - 공간 복잡도 O(2M) = 80Mb

 

1. 모든 가능한 메모리 값에 대해 최소 비활성화 cost를 구하는게 아닌, 모든 가능한 cost값에 대해 최대 확보 메모리를 구한다

 

2. cost는 1~100이므로, 시간/공간 복잡도 문제 없음

 

3. 일반적 냅색처럼 DP로 하나씩 추가해 나간다

 

4. 확보 메모리 M이 가능한 최소 cost를 구하는게 목적이므로, 최종 DP결과를 오름차순으로 탐색하며 최초로 M 이상 확보된 순간이 정답

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = pint(st.nextToken());
		M = pint(st.nextToken());
		
		memory=new int[N];
		cost=new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			memory[i]=pint(st.nextToken());
		}
		
		int totalCost=0;
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			cost[i]=pint(st.nextToken());
			totalCost+=cost[i];
		}
		
		int[] dpCur = new int[totalCost+1];
		int[] dpPrev = new int[totalCost+1];
		for (int i = 0; i < N; i++) {
			//i번째 물건을 고려했을때
			for (int j = 0; j < dpPrev.length; j++) {
				if(j<cost[i])dpCur[j]=dpPrev[j];
				else dpCur[j] = Math.max(dpPrev[j], dpPrev[j-cost[i]] + memory[i]);
			}
			dpPrev = dpCur.clone();
		}
		
		for (int i = 0; i < dpCur.length; i++) {
			if(dpCur[i]>=M) {
				System.out.println(i);
				break;
			}
		}
		
		
	}
	static int minCost, N, M;
	static int[] memory;
	static int[] cost;
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면