BOJ G3 7579 앱 JAVA

7579번: 앱

 

---

문제 읽기

문제를 계속 읽다 보니 0/1 냅색 문제가 생각났다. 그래서 그 문제처럼 해보려고 했더니..@@ 메모리 용량의 범위가 너무 컸다. DP 2차원 배열을 선언한다면, 앱 개수 * 메모리 = 100x10,000,000 = 10억이었다. 절대 ! 안된다.

 

사실 메모리 계산하는 방법을 확실히 몰라서 찾아봤다.

글 읽기 - 메모리 초과... 128 mb이면 int형 몇개?까지 선언가능한가요??

 

요약하면 128MB의 경우 int형 3000만개까지 가능하다. 억 단위로 넘어가면 불가능하다고 생각하면 될 것 같다.

이렇게 되니 어떻게 접근할 지 감이 안 왔다. 비용을 j로 해야 하나? 하는 생각이 문득 들었지만, 경험해본 적이 없어서 잘 와 닿지 않았다. 그런데 질문 게시판 뒤적 거리다 언뜻 보는 바람에 그 방식으로 한 번 해봤다.

---

문제 풀기

일단 그려봤다. 사실 처음에 이렇겠지? 하고 생각하며 그린 거라서 틀린 부분도 존재한다.

그래도 이걸 보면 대충 감이 잡힐 것이다.

 

일단 나는 dp[개수][비용] 배열을 만들어, 그 값으로는 해당 어플을 해당 비용을 사용해서 확보할 수 있는 용량의 최댓값을 넣어주었다.

 

즉, 다음과 같이 정리할 수 있다.

dp[i][j] = val
i : 1~N번째 앱이 삭제 후보인 상황에서,
j : 비용을 j만큼 사용해서
val : 확보할 수 있는 메모리 용량의 최댓값

 

표를 차분히 그리다 보면, 다음과 같은 점화식을 얻을 수 있다.

DP[i][j] = DP[i-1][j] (j < cost[i])

• 해당 비용으로는 앱을 다시 복구하지 못하기 때문에 삭제하지 못한다. 즉, 확보할 수 있는 메모리 공간이 없다. ⇒ DPi[i-1][j]

DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j-cost[i]] + memory[i])

• 해당 비용으로는 앱을 복구할 수 있기 때문에 당장은 삭제할 수 있다 ⇒ DP[i-1][j-cost[i] + memory[i]
• 하지만 삭제하지 않는 경우가 이득일 수 있기 때문에 ⇒ DP[i-1][j]
• 둘 중 메모리 용량의 최댓값을 저장한다.

 

이를 코드로 작성하면 된다

---

실수한 부분

j의 범위. j의 최댓값

처음에는 j는 단순히 cost이기 때문에 cost의 범위를 따라가면 된다고 생각했다. 그래서 100으로 했었는데 계속 틀렸다. 그런데 맞왜틀만 외치고 전혀 몰랐다..

하지만.. 진짜 그건 아니다. 내가 그림을 그리면서도 생각했지만, j는 결국 하나의 앱에 대한 비용이 아니라 DP[N][j]까지 가면 N개의 비용이 된다. 따라서 N의 크기 * cost의 크기 = 10000만큼이 필요하다! 0~10000이니까 10001을 선언해주자. 그럼 정답!

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_G3_7579_앱 {
    static class App{
        int memory;
        int cost;
        public App(int memory, int cost){
            this.memory = memory;
            this.cost = cost;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        App[] A = new App[N+1];
        st = new StringTokenizer(in.readLine());
        StringTokenizer st2 = new StringTokenizer(in.readLine());
        for (int i = 1; i < N+1; i++){
            A[i] = new App(Integer.parseInt(st.nextToken()), Integer.parseInt(st2.nextToken()));
        }

        int[][] dp = new int[N+1][10001];
        int minCost = Integer.MAX_VALUE;
        for (int i = 1; i < N+1; i++){
            for (int j = 0; j < 10001; j++){
                dp[i][j] = dp[i-1][j];
                if (j >= A[i].cost)
                    dp[i][j] = Math.max(A[i].memory + dp[i-1][j-A[i].cost], dp[i][j]);

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