b7579. 앱

 

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

 

 

 

이문제를 접했을때 어떤 알고리즘을 풀어야 할지 몰라 풀이방법을 찾아보니

DP로 풀어야 함을 알 수 있었다.

 

int[][] dp배열을 선언하고

dp[i][j] 에서 i 는 i번째의 앱까지 고려하였을 경우를 의미하고

j는 가능한 비용의 경우의 수를 의미한다.

먼저 입력값을 받아 실행 중인 앱의 개수 N, 필요한 메모리 M,
각 앱의 메모리 사용량과 비활성화 비용을 각각 m과 c 배열에 저장한다.
DP 배열은 비용의 최대값(10000)까지 고려할 수 있도록 초기화한다
.
DP 계산 과정은 각 앱을 순차적으로 처리하면서 진행된다.
i번째 앱을 고려할 때, 현재 비용 j로 확보 가능한 메모리를 갱신한다.
만약 j가 c[i]보다 크거나 같다면,

i번째 앱을 비활성화하는 경우와 하지 않는 경우 중 더 큰 메모리를 선택한다.

그렇지 않은 경우,

이전 앱까지의 결과를 그대로 유지한다.

 

DP 배열을 채우면서,

현재 확보한 메모리가 M 이상일 경우 해당 비용 j를 최소 비용으로 갱신한다.

마지막으로, 최소 비용을 출력하여 문제를 해결한다.  

 

 

import java.io.*;
import java.util.Arrays;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    static int N,M,mininumAnswer=Integer.MAX_VALUE;
    static int[] m,c;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 실행되고 있는 앱수
        M = Integer.parseInt(st.nextToken()); // 필요한 메모리수
        m = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        c = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        dp = new int[N][10001];

        //첫 원소를 포함하는 경우의 수 ~ 마지막원소를 포함하는 경우의수
        for(int i = 0 ; i < N ; i++) {
            int cost = c[i];
            int memory = m[i];
            for (int j = 0; j < 10001; j++) {
                if (i == 0){
                    if (j >= cost) dp[i][j] = memory;
                }else{
                    if (j >= cost){
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-cost]+memory);
                    }else {
                        dp[i][j] = dp[i-1][j];
                    }
                }
                if(dp[i][j] > M){
                    mininumAnswer = Math.min(mininumAnswer,j);
                }
            }
        }
        System.out.println(mininumAnswer);
    }
}