백준 7579번: 앱 (Python)

접근

메모리가 아닌 코스트를 기준으로 하는 냅색 문제이다. 길이가 sum(cost) + 1 인 리스트 n + 1 개를 가진 dp를 만들어 다음과 같이 채워나간다.

dp[i][j] = i 번째까지의 앱과 j의 코스트를 가지고 확보 할 수 있는 최대 메모리 값

1. cost[i] > j 일 경우 cost 부족으로 i 번째 앱 비활성화 불가능
2. 그렇지 않을 경우 dp[i - 1][j] 와 dp[i - 1][j - cost[i]] + memory[i] 값 중 최대값 (j 코스트로 확보할 수 있는 최대 메모리)

순환하면서 최초로 목표 메모리를 넘는 j 값을 저장해준다. 이 과정의 일부를 표로 표시하면 다음과 같이 순환하게 된다.

	cost	0	1	2	3	4	5	6	7
memory	0	0	0	0	0	0	0	0	0
30	3	0	0	0	30	30	30	30	30
10	0	10	10	10	40	40	40	40	40
20	3	10	10	10	40	40	40	60	60
35	5	10	10	10	40	40	45	60	60
40	4	10	10	10	40	50	50	60	60

코드

import sys

n, m = map(int, sys.stdin.readline().split())
memory = [0] + list(map(int, sys.stdin.readline().split()))
cost = [0] + list(map(int, sys.stdin.readline().split()))
dp = [[0 for _ in range(sum(cost) + 1)] for __ in range(len(cost) + 1)]
result = sum(cost)
for i in range(1, len(cost)):
    for j in range(len(dp[1])):
        if cost[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j - cost[i]] + memory[i], dp[i - 1][j])

        if dp[i][j] >= m:
            result = min(result, j)
if m != 0:
    print(result)
else:
    print(0)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!