[Baekjoon] 앱

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

설명 : N과 M이 주어지고, N개의 App에 대해 각각 사용중인 Bytes와 비활성화 했을 시에 대한 비용들이 주어진다. 이때 Mbytes를 확보하기 위한 최소한의 비용을 구하는 문제이다.

처음 문제를 접했을 때, DP로 풀어야 겠다는 감은 왔지만...정말 오랜 시간이 걸린 문제이다.

풀이 : 

Mbytes를 확보하기 위해 드는 최대 비용은 당연 모든 비용들을 합한 값이다

따라서 이 비용들을 배열의 인덱스로 잡고, DP를 풀어나갔다. (반복문을 돌며(App을 하나씩 거치며), 최소값을 수정해나갔다.)

그러나 결과는....'실패' 였다.

연습장에 표를 그리고 예제들을 써내려가보았다.

그리고 알게 된 사실...

예제에서는 비용이 3, 0, 3, 5, 4 순서대로 들어온다. 하지만 이런 순서대로 들어오면, 최적의 해를 보장하지 못한다.

루프를 돌며, 값을 갱신시키는데 전에 사용했던 값(App)을 또 다시 사용할 수 있기 때문이다.

따라서 비용을 기준으로, 우선 오름차순 정렬한 후 반복문을 돌면 최적의 해를 찾을 수 있다.

코드 :

package feb13.app;
 
import java.util.Scanner;
 
 
public class Main {
 
    class App {
        
        int using, cost;
 
        public App(int using, int cost) {
            super();
            this.using = using;
            this.cost = cost;
        }
        
    }
 
    public void selectionSort(App[] arr){
        
        for(int i = 0; i < arr.length; i++){
            
            int minIndex = i;
            for(int j = i; j < arr.length; j++){
                if(arr[j].cost < arr[minIndex].cost){
                    minIndex = j;
                }
            }
            App temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        int N, M;
        int max_cost = 0;
        int[] dp;
        App[] app;
        Scanner sc = new Scanner(System.in);
        Main m = new Main();
        
        N = sc.nextInt();
        M = sc.nextInt();
        app = new App[N];
        
        for(int i = 0; i < N; i++)
            app[i] = m.new App(sc.nextInt(), 0);
    
        for(int i = 0; i < N; i++){
            int cost = sc.nextInt();
            app[i].cost = cost;
            max_cost += cost;
        }
        dp = new int[max_cost + 1];
        
        m.selectionSort(app);
 
        for(int i = 0; i < N; i++){
            
            int using = app[i].using;
            int cost = app[i].cost;
            boolean[] visited = new boolean[max_cost + 1];
            
            int max = 0;
            for(int j = dp.length - 1; j >= cost; j--){
                
                int diff = j - cost;
                
                if(!visited[diff]){
                    if (dp[diff] + using > dp[j]) {
                        dp[j] = dp[diff] + using;
                        visited[j] = true;
                        max = dp[j];
                    } 
                }
                else {
                    dp[j] = max > dp[j] ? max : dp[j];
                    visited[j] = true;
                }
            }
            
        }
        
        /*for(int i = 0; i < dp.length; i++){
            System.out.println(i + ": " + dp[i]);
        }*/
        for(int i = 0; i < dp.length; i++){
            if(dp[i] >= M){
                System.out.println(i);
                break;
            }
        }
    }
 
}