[백준] 7579번: 앱

문제

백준 - 7579번: 앱

분석

N개의 앱에 대한 메모리와 비활성화 하는데 드는 비용 정보, 새로운 앱 B를 실행하는데 필요한 메모리 M바이트에 대한 정보가 주어졌을 때 비용의 합을 최소화해서 M 바이트를 확보하는 방법을 구하는 문제이다.

이 문제는 KnapSack 알고리즘을 사용하고, 전형적인 배낭문제 12865번: 평범한 배낭에서 살짝 응용을 하면 된다.

문제에서 최소 비용이라는 말 때문에 dp 배열에 비용을 담아서 풀다가 틀렸다.
i를 앱 종류, j를 사용한 비용, dp[i][j]를 확보한 메모리로 하면 쉽게 해결할 수 있다.

메모리는 j비용 내에서 최대한 확보한다.
i번째 앱을 비활성하는데 드는 비용이 현재까지 든 비용 j보다 크다면 이 앱은 비활성할 수 없으므로 i를 고려하기 전 dp[i-1][j]의 값을 그대로 얻는다.
만약 j보다 작거나 같다면 앱을 비활성화해도 되고, 안해도 된다. 따라서 두 가지 경우 중 더 큰 값을 취한다. 비활성화 하는 경우는 i를 고려하기 전[i-1]에다가 j에 현재 드는 비용을 뺀[j-c[i]] 즉, dp[i-1]j-c[i]]에 m[i]를 더한 경우다.

dp를 채우고, dp[i][j]값이 M 이상인 경우 중에 j가 최소가 되는 값을 얻으면 최소 비용을 얻을 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
m = [0]+list(map(int, input().split()))
c = [0]+list(map(int, input().split()))
MAX_COST = sum(c)
dp = [[0]*(MAX_COST+1) for _ in range(N+1)]
ans = MAX_COST
for i in range(1, N+1):
    for j in range(MAX_COST+1):
        if j >= c[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+m[i])
        else:
            dp[i][j] = dp[i-1][j]
        if dp[i][j] >= M:
            ans = min(ans, j)
print(ans)

어떤 앱은 처리 비용이 0인 경우가 있으므로 j는 0부터 시작해야 한다.

끝으로..

비슷한 문제를 살짝 응용한 것인데 조금 헤맨것 같다.
더 유연한 사고를 길러야겠다.