[JAVA] 백준 7579 - 앱

 

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

 

DP 풀이

Knapsack문제를 완벽히 체득하고 외울정도까지 되었으면 이를 응용하는버전으로 구할수있다.

하지만 주의해야할건 dp[i][w]에서 1~i까지 어플중에 메모리가 w일때 최소 시간 이라고 정의하면, 메모리 부족이 뜬다.

dp[i][t] =  1~i까지 어플이있을때, t시간을 소요하는 최대 메모리

라고 dp를 선언할수 있느냐 없느냐를 물어보는게 이문제의 핵심같다.

 

그렇게하면 점화식을 다음과 같이 세울 수 있다

 

dp[i][t] => max(dp[i -1][t - cost[i]] + memory[i] ( i번째를 담았을 때) , dp[i - 1][t] (i번째를 안담았을 때))

 

그후 0이 엣지케이스이므로 index문제만 해결해주면된다.

 

왜 최대 메모리를 dp에 저장하느냐면, 결론적으로 dp[i][t]의 최대메모리가 M을 넘냐 안넘느냐가 중요하기때문이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    static int N;
    static int M;
    static int[] memories;
    static int[] times;
    static int[][] dp;
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        N = Integer.parseInt(lines[0]);
        M = Integer.parseInt(lines[1]);
        dp = new int[N + 1][10001];

        lines = br.readLine().split(" ");
        memories = new int[N + 1];
        times = new int[N +1];
        for(int i = 1 ; i <= N ; i++){
            memories[i] = Integer.parseInt(lines[i - 1]);
        }
        lines = br.readLine().split(" ");
        for(int i = 1 ; i <= N ; i++){
            times[i] = Integer.parseInt(lines[i - 1]);
        }
        for(int i = 1 ; i <= N ; i++){
            int cost = times[i];
            for(int j = 0 ; j <= 10000 ; j++){
                if(j - cost >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost] + memories[i]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }

                if(dp[i][j] >= M){
                    ans = Math.min(ans,j);
                }
            }
        }
        System.out.println(ans);

    }


}

DFS + 가지치기를 이용한 풀이

이러한 문제는 

시간초과(메모리 부족)가 나는게 확실하긴 하지만 일단 재귀함수로 빠르게 코드를 구현하고,

메모이제이션으로 가지치기를 적당히 해서 이를 해결하는 전략이 가장 유용한것같다.(실전에선 부분점수라도 받을 수 있으니까..)

 

dp[i][time]에 그 시간에 얻을 수 있는 최대의 메모리를 저장해두고,

똑같은 dp[i][time]이 올떄, 그것과 비교해서 그것과 메모리가 작으면 더이상 탐색하지 않아야한다.

 

i , i + 1 , i + 2..의 점화식으로 구성되는 dp문제보다

이러한 메모이제이션 dp문제가 더욱 까다롭지만, 많이 풀어보니 푸는 루틴이 어느정도 정해진 것 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    static int N;
    static int M;
    static int[] memories;
    static int[] times;
    static int[][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        N = Integer.parseInt(lines[0]);
        M = Integer.parseInt(lines[1]);
        dp = new int[N + 1][10001];

        lines = br.readLine().split(" ");
        memories = new int[N + 1];
        times = new int[N +1];
        for(int i = 1 ; i <= N ; i++){
            memories[i] = Integer.parseInt(lines[i - 1]);
        }
        lines = br.readLine().split(" ");
        for(int i = 1 ; i <= N ; i++){
            times[i] = Integer.parseInt(lines[i - 1]);
        }
        dfs(0,0,0);
        for(int i = 0 ; i <= 10001 ; i++){
            if(dp[N][i] >= M) {
                System.out.println(i);
                break;
            }
        }


    }
    static void dfs(int i , int memory, int time){
        //이미 더 작은 값 잇을때 가지치기
        if(dp[i][time] != 0 && dp[i][time] >= memory){
            return;
        }
        dp[i][time] = memory;
        if(i >= N) {
            return;
        }
        dfs(i + 1 , memory, time); // 안끌떄
        dfs(i + 1 , memory + memories[i + 1] , time + times[i + 1]); //끌때
    }

}