[백준 / BOJ] 7579 앱 (Java)

문제

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

7579번: 앱

 

스마트폰 백그라운드에 켜져있는 N개의 애플리케이션중 몇개의 애플리케이션을 종료해서 M만큼의 메모리를 확보하고싶다.

각 애플리케이션을 종료할때얻는 메모리양과 종료할때 필요한 비용이 주어질때, M만큼의 메모리를 확보하기위해 필요한 최소 비용을 구하는 문제다.

 

 

---

풀이

knapsack 문제였다.

개인적으로 dp배열을 생각하는게 어려웠다.

 

2차원 배열을 이용해 푸는것은 맞는것 같은데,

M이 10,000,000까지 가므로, dp배열에 M을 집어넣으면 배열 선언자체가 안된다.

따라서, M이아닌,  dp[사용가능한 cost][N] = 현재까지 얻은 M의 최댓값 이런식으로 만들어서 구해야한다.

- 사용가능한 cost의 경우, (한 앱의 코스트가 최대 100이고 앱은 최대 100개가 있으므로,) 최대 100*100 이다

 

이 외에는 기본적인 knapsack 풀듯이 풀면된다.

    private int getMinimumCost(){
        for(int ableCost = 0; ableCost <= 100*100; ableCost++){
            for(int appNum = 1; appNum <= N; appNum++){
                if(ableCost > 0)dp[ableCost][appNum] = Math.max(dp[ableCost-1][appNum],dp[ableCost][appNum]);
                dp[ableCost][appNum] = Math.max(dp[ableCost][appNum-1],dp[ableCost][appNum]);
                App app = applications.get(appNum);
                if(app.cost <= ableCost) {
                    dp[ableCost][appNum] = Math.max(
                    dp[ableCost-app.cost][appNum-1]+app.memory
                    ,dp[ableCost][appNum]
                    );
                }
                if(dp[ableCost][appNum] >= M) return ableCost;
            }
        }
        return 100*100; // 모든 앱을 비활성화 해야할때
    }

 

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/7579%20%EC%95%B1/Main.java

devxb/JJUNalgo