[Java] 백준7579 - 앱

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

7579번: 앱

N 범위가 100까지인것도 모르고 DFS 사용했다가 큰일날뻔 했다...😅

 

 

 

재귀함수 호출은 Stackoverflow를 유발하니 조심하자 (밑 링크 참조)

http://www.tcpschool.com/c/c_memory_stackframe

코딩교육 티씨피스쿨

 

 

이 문제는 배낭 채우기랑 비슷하다. 

배낭 채우기는 용량, 무게 중심인데, 여기는 비용, 메모리 중심이다.

여러 개 중에서 몇개 골라서 목표하는 조건을 이루는 것들 중에 가장 최선의 값을 도출하는 것이다.

 

이런 유형의 문제는 DP를 사용하는 건데, 점화식 세우느라 너무x100 머리아프다😭 근데 어쩌겠어..해야지

 

 

※ DP 구성은 다음과 같다

DP[앱의 개수][특정 비용] = 최대 메모리

 

※ 점화식

DP[ i ] [ j ]  =  MAX( DP[ i - 1 ] [ j ] , DP [ i - 1 ] [ j - 현재 비용 ] + 현재 메모리 )

 

설명

• 현재 앱을 추가하려고 함 → 총 i개

1. DP[ i - 1 ] [ j ] = 현재 앱이 없고, 총 비용이 j인 경우의 최대 메모리

2. DP[ i - 1 ] [ j - 현재 비용] + 현재 메모리 = 현재 앱이 없고, 현재 비용만큼 작은 경우의 최대 메모리에 현재 메모리를 더함

• 1번과 2번을 비교해서 최대값을 넣음
• 1번은 i - 1만 고려하면 된다. → 왜냐하면 i - 1일때 i - 2 인경우를 고려해서 나온 결과값이기 때문

 

※ 근데 나는 비용이 0인 경우는 입력받을 때 그냥 메모리에서 다 차감시켰다.

 

[코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class boj7579 {
	static class App{
		int memory, cost;
		public App(int memory, int cost) {
			this.memory=memory;
			this.cost=cost;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		String[] m = br.readLine().split(" ");
		String[] c = br.readLine().split(" ");
		
		ArrayList<App> arr = new ArrayList<>();
		
		// 0인거 모두 비활성화
		for(int i=0; i<N; i++) {
			int mem = Integer.parseInt(m[i]);
			int cos = Integer.parseInt(c[i]);			
			
			if(cos==0) {
				M -= mem;
				continue;
			}
			
			arr.add(new App(mem, cos));
		}
		
		if(M<=0) {
			bw.write("0");
			bw.flush();
			bw.close();
			return ;
		}
		
		int size = arr.size();
		if(size==1) {
			if(arr.get(0).memory>=M)
				bw.write(arr.get(0).cost+"");
			else
				bw.write("0");
			bw.flush();
			bw.close();
			return ;
		}
		
		
		// N 최대 = 100 * C 최대 100 = 10000
		int MAX = 10000;
		
		// dp [앱의 개수] [특정 비용] = 최대 메모리
		int[][] dp = new int[size][MAX+1];
		int[] cost = new int[size];
		int[] memory = new int[size];
		
		int answer = Integer.MAX_VALUE;
		
		// 앱 개수
		for(int i=0; i<size; i++) {
			App app = arr.get(i);
			
			// 총 비용
			for(int j=0; j<=MAX; j++) {
				// 앱이 1개
				if(i==0) {
					if(j >= app.cost) dp[i][j] = app.memory;
					continue;
				}
				
				if(j >= app.cost) {
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-app.cost]+app.memory);
				}else {
					//System.out.println(i+":"+j);
					dp[i][j] = dp[i-1][j];
				}
				
				if(dp[i][j] >= M)
					answer = Math.min(answer, j);
			}
		}
		
		bw.write(answer+"");
		bw.flush();
		bw.close();
	}
}