문제링크

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

구현방법

N개의 앱 a1 ~ an 이 활성화되있다고 가정

ai는 각각 mi만큼 메모리 사용

• ai를 비활성화 한후 다시 실행시 추가적으로 들어가는 비용 ci

B를 실행하고자 하면 M 바이트의 추가 메모리가 필요할 때 현재 활성화 되어있는 앱 ai~ an 중 몇개를 비활성화 해서 M 바이트를 추가로 확보해야한다.

• 그중에서 비활성했을 경우의 비용 의 합을 최소화하여 메모리 바이트를 확보하는 법을 찾기.

1. M바이트이상 확보가 되는가?
2. 이것이 현재까지의 최소비용인가?

핵심 로직

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

dp[i][j] = Math.max(dp[i-1][j-현재사용하는 비용] + 현재 비워지는 메모리크기,dp[i-1][j]);

//만약 m바이트 이상이 만족되면 최소비용을 적어놓은 res와 j를 비교해서 최소비용 갱신
if(dp[i][j] >= m){
    res = Math.min(res,j);
}

메모리를 중점으로 생각해서 나아가야하는 문제다.

• 최소비용을 중점으로 하게 되면 현재 조건인 m바이트 이상이라는 조건을 만족하는 방법을 찾기 어렵다.
  • 그렇기 때문에 메모리를 중점으로 생각해서 현재 조건인 m바이트 이상일 때 들어가는 비용이 최소인지 갱신하는 방법을 이용하는거같다.

알고리즘

• DP

• 배낭 문제

CODE

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];
        int cost[] = new int[n];

        int [][] dp = new int[n][100001];

        StringTokenizer memoryToken = new StringTokenizer(br.readLine());
        StringTokenizer costToken = new StringTokenizer(br.readLine());


        for(int idx = 0; idx <n;idx++){
            memory[idx] = Integer.parseInt(memoryToken.nextToken());
            cost[idx] = Integer.parseInt(costToken.nextToken());
        }

        int res = Integer.MAX_VALUE;
        for(int appnum = 0; appnum <n;appnum++){
            int curCost = cost[appnum];
            int curMemory = memory[appnum];


            for(int check = 0; check<=10000;check++){

                if(appnum == 0){
                    if(check >= curCost) dp[appnum][check] = curMemory;

                }else{
                    if(check >= curCost){
                        dp[appnum][check] = Math.max(dp[appnum-1][check - curCost] +curMemory,dp[appnum-1][check]);

                    }else{
                        dp[appnum][check] = dp[appnum-1][check];
                    }
                }

                if(dp[appnum][check] >= m){
                    res = Math.min(res,check);
                }
            }
        }
        System.out.println(res);

    }
}