[백준] 7579번 : 앱 (JAVA)

인간몽쉘김통통·2024년 7월 6일

다이나믹 프로그래밍 배낭 문제 백준 알고리즘

백준

목록 보기

72/92

문제

이해

N개의 앱이 주어집니다. N개의 앱은 각자 필요한 메모리 정보와 비활성 시 필요한 비용 정보가 있습니다.

필요한 메모리 M 바이트를 확보하기 위해 N개의 앱 중에서 비활성해야 합니다. M 바이트를 확보하기 위한 최소의 비용을 출력해야 합니다.

접근

가장 직관적인 방법은 M 바이트를 확보하기 위해 N개의 앱간의 조합을 모두 탐색하는 것입니다. 하지만, 부분 집합의 경우 N이 최대 100개이기 때문에 2^100의 시간이 필요합니다.

따라서, 탐색을 최적화하는 DP를 사용해야 합니다. N개를 선택하여 최소 M 바이트를 선택한다? 바로 배낭문제와 유사합니다.

기존의 배낭 문제와 비교해봅시다. 배낭문제는 무게와 가치가 주어집니다. 제한된 무게 안에서 최대 가치를 구해야 합니다. 배낭 문제의 기본 DP 원리는 무게를 기준으로 어떠한 물건이 가방에 포함될 수 있는지에 대한 여부를 판단합니다. i번째, j무게를 판단할 때 만일 i번째 무게가 j보다 크다면 가방에 넣을 수 없기 때문에 i번째 물건은 제외해야 합니다. 반대로 가능하다면 i번째 물건을 넣은 채 DP테이블을 갱신합니다.

본 문제에 대입해봅시다. 먼저 메모리를 생각해봅시다. 제한된 메모리에 따라 앱이 포함될 수 있는지를 판단할 수 있을까요? 없습니다. 문제에서는 메모리는 최소 M바이트 이상이면 되기 때문에 메모리는 그 이상 포함되어도 문제의 조건에 만족합니다.

그렇다면 비용은 어떨까요? j의 비용에서 i번째 앱이 포함될 수 있는지 판단할 수 있을까요? 있습니다. 제한된 비용에 따라서 i번째 비용이 더 작다면 포함될 수 있고 없다면 포함될 수 없습니다. 본 문제에서의 비용이 곧 배낭 문제의 무게를 의미합니다.

문제의 조건을 보면 비용은 최대 100이며 앱도 최대 100개가 존재합니다. 따라서, 존재할 수 있는 비용 합의 최댓값은 100x100 입니다. 이를 활용하여 DP 테이블을 구성할 수 있습니다. 점화식은 배낭 문제의 점화식과 같습니다.

정답은 비용의 최솟값을 원하기 때문에 DP[N][j]가 M이상인 최소 j가 정답이 되겠습니다.

풀이

        dp = new int[N + 1][10001];
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= 10000; j++) {
                if (j < cost[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);
                }
            }
        }