[백준] 7579번. 앱

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

7579번: 앱

 

풀이 

다이나믹 프로그래밍 / 배낭 문제 

 

제한된 비용이 주어졌을 때 최대로 얻을 수 있는 메모리 를 DP 로 해결하면 된다. 

배낭 문제와 거의 동일하다. 

 

dp[i][j] = i 번째 앱 까지 포함했을 때, j 의 비용으로 얻을 수 있는 메모리 

 

dp[i][j] = Max ( dp[i-1][j] , dp[i-1][j-cost[i]] + m[i] )

 

i 번째 앱을 끄지 않았을 때 / i 번째 앱을 껐을 때 를 비교해서 제한 비용 내 더 많은 메모리를 얻을 수 있는 것을 선택한다. 

 

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        
        String[] tmp = reader.readLine().split(" ");
        int N = Integer.parseInt(tmp[0]);
        int M = Integer.parseInt(tmp[1]);
        
        String[] tmp2 = reader.readLine().split(" ");
        int[] m = new int[N];
        
        for(int i = 0; i<N; i++) {
            m[i] = Integer.parseInt(tmp2[i]);
        }
        
        String[] tmp3 = reader.readLine().split(" ");
        int[] c = new int[N];
        int total = 0;
        
        for(int i = 0; i<N; i++) {
            c[i] = Integer.parseInt(tmp3[i]);
            total += c[i];
        }
    
        // dp[i][j] = i 번째 앱까지 포함했을 때, j 비용으로 얻을 수 있는 최대 메모리
        // dp[i][j] = dp[i-1][j] or dp[i-1][j-cost[i]] + M[i]
        
        int[][] dp = new int[N][total + 1];
        for(int j = 0; j<=total; j++) {
            if (j < c[0]) {
                dp[0][j] = 0;
            } else {
                dp[0][j] = m[0];
            }
        }
        
        for(int i = 1; i<N; i++) {
            for(int j = 0; j<=total; j++) {
                dp[i][j] = dp[i-1][j];
                if (j - c[i] >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-c[i]] + m[i]);
                }
            }
        }
        
        for(int i = 1; i<=total; i++) {
            if (dp[N-1][i] >= M) {
                System.out.println(i);
                break;
            }
        }
    }
}