백준 7579번 : 앱 in Python

7579번: 앱

 

www.acmicpc.net

이 문제는 새 앱을 활성화하기 위해 메모리에 있는 기존 앱을 비활성화하려 하는데, 기존 앱을 비활성화하는 경우 재사용할 때의 시간을 고려해 기존 앱을 종료시키려 할 때 이 시간을 최소화할 수 있는 앱들을 선택하는 문제다.

원래 이 문제는 기존의 냅색 문제와 매우 유사한 문제로, N+1과 기존 앱들이 모두 활성화되어 있을 때 메모리 크기를 행과 열로 하는 행렬을 만들어 dynamic programming을 적용해서 풀 수 있다. 그러나 문제는 이 문제의 입력 크기에서 메모리 크기가 최대 100 * 10^7 = 10^9까지 늘어나기 때문에 이 행렬을 만들기만 해도 메모리 초과로 실패한다. 그래서 이 문제는 약간의 발상의 전환이 필요하다. 

다행이게도 각 앱 당 재사용 시간의 합이 100 * 100 = 10^4 이하이기 때문에 이를 행렬의 열로 한다. 그러면 행렬의 원소의 개수가 많아도 100 * 10^4 = 10^6 이므로 메모리 초과 문제가 발생하지 않는다. 이제 이 문제를 해결하기 위해 각 원소를 어떻게 구해야 할지 결정하자.

냅색 문제를 푸는 것과 유사하게 행렬의 (i, j) 원소가 나타내는 값을 i번째 앱까지만 고려할 때 총 재사용 시간이 j 이하가 되도록 앱을 비활성화할 때 얻을 수 있는 메모리 용량의 최댓값이라고 하자. 그러면 N번째 행의 원소들은 모든 앱을 고려할 때 총 재사용 시간에 따라 얻을 수 있는 메모리 용량의 최댓값을 얻을 수 있다. 이 때 이 N번째 행의 원소들을 (N, 1)부터 살펴보면서 가장 먼저 원소의 값이 M 이상인 경우가 나올 때 그 때 그 원소의 열이 총 재사용 시간의 최솟값이 될 것이다.

이제 (i, j) 원소를 어떻게 구할지 생각해보자. 우선 i = 0이면 base case로 모든 앱을 고려하지 않는 경우이므로 메모리 용량 역시 0일 것이다. 그래서 (0, j)는 0으로 설정한다. 그리고 i > 0일 때 (i, j)는 i번째 앱을 고려하는데, 만약 i번째 앱의 재사용 시간이 j보다 크면 i번째 앱을 비활성화하면 총 재사용 시간이 j보다 커지므로 i번째 앱을 비활성화하면 안 된다. 그래서 (i, j) 원소는 (i-1, j) 원소를 그대로 가져온다. 반면에 i번째 앱의 재사용 시간이 j보다 작거나 같으면 i번째 앱을 비활성화할 수 있으므로 i번째 앱을 비활성화하는 것을 포함해 얻을 수 있는 최대 메모리 용량과 i번쨰 앱을 비활성화하지 않는 경우 얻을 수 있는 메모리 용량의 최댓값과 비교해 더 큰 값을 (i, j) 원소에 넣는다.

이를 코드로 구현하면 다음과 같다.

import sys
N, M = map(int, input().split())
byte = [0] + list(map(int, input().split()))
costs = [0] + list(map(int, input().split()))

cost_sum = 0
for cost in costs:
    cost_sum += cost
# (N+1)*(비용의 합+1) 크기의 dynamic programming을 위한 행렬을 만든다. 
dp = [[0]*(cost_sum+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, cost_sum+1):
        # i번째 앱의 비용이 j보다 크면 i번째 앱을 비활성화하는 것이 불가능하다.
        if costs[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-costs[i]]+byte[i], dp[i-1][j])
minimum_cost = sys.maxsize
for i in range(cost_sum+1):
    if dp[N][i] >= M:
        minimum_cost = min(minimum_cost, i)
print(minimum_cost)