[7579] 앱 (백준)

가장 적은 비용을 출력한다.

배낭문제를 응용한 문제였다. 처음에 문제를 보고 모든 경우를 탐색해서 메모리를 확보한다면 n개의 앱중에 몇개를 선택해서 종료하여야 하므로 2^n개의 경우가 나와 시간 초과가 날 것으로 생각해 DP를 이용해서 풀었다. 그리고 처음에는 dp의 y축을 메모리제한으로 생각해서 파이썬 2차원 배열의 범위초과 (100*10000000)가 나오기도 했다.

 

그럼 기본 배낭문제와 이 문제가 다른점은 무엇일까? 위 문제는 드는 비용을 y축으로 설정한다는 점이 다르다. 그리고 dp배열이 가지는 값은 확보할 수 있는 최대 메모리가 된다. 처음부터 생각해보면

1. 어떤 앱을 종료할 때
2. 그렇지 않을 때

가 존재하고 이는 그 앱을 비활성화함으로써 드는 비용을 반영할수 있거나 혹은 반영하지 않음을 결정하게 된다(모든 앱을 비활성화한다는 가정하에 비용이 최대로 들 수 있다). 즉 고정비용이 든다고 생각하고 최대로 메모리를 확보하게 되는 dp배열을 bottom-up방식으로 채워나가는 것이다.

 

한편, 중요조건 중에 하나는 메모리를 M이상 확보하는 것인데, 이 말인즉슨, M이상 확보하기만 하면 앱을 어떤 방식으로 비활성화 하더라도 최소한의 비용으로 종료하는 경우를 알수있음을 의미한다. 

 

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
ms = [0]+list(map(int, input().rstrip().split()))
cs = [0]+list(map(int, input().rstrip().split()))
cend = sum(cs)
mc = list(zip(ms, cs))
dp = [[0]*(cend+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, cend+1):
        mem, cost = mc[i][0], mc[i][1]
        if j >= cost:
            dp[i][j] = max(dp[i-1][j-cost]+mem, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
            
min_c = cend                            # 가장 큰 비용을 설정하고
for i in range(1, n+1):
    for j in range(cend+1):
        if dp[i][j] >= m:               # m이상 확보된 메모리에 대해
            min_c = min(min_c, j)       # 최소 비용을 업데이트한다
print(min_c)

의견 및 피드백은 언제나 환영입니다