[Baekjoon]백준 7579 앱(골드 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 N개의 메모리의 바이트 수와 비용이 주어져있다 그리고 M 바이트를 확보하기 위하여

지불해야하는(?) 비용의 최솟값을 구하는 것이 문제이다

예제를 통해 설명하자면 60바이트를 확보하기 위해 30 10 20 바이트를 각각 활용하여 6의 비용으로

60바이트의 메모리 확보가 가능하다 그리고 이 값은 최솟값이 된다(20 40 의 경우 3+4, 총 7의 비용이 들기 때문)

 

그래서 이번엔 어떠한 점화식을 구해야할지 고민을 해보았다

처음에는 dp[필요한 바이트 수]로 구현을 해보다가 과정이 매끄럽지 않아서

dp를 2차원 배열로 생각해보다가 dp[i][j](i번째 앱까지 j 비용으로 가능한 최대 byte)로 선언하여 코드를 작성하였다

 

그냥 머릿속으로 생각하기에는 복잡하여서 표를 그린 후에 코드를 작성할 수 있었다

		0	1	2	3	4	5	6
byte	cost	0	0	0	0	0	0	0
30	3	0	0	0	30	30	30	30
10	0	0	10	10	40	40	40	40
20	3	0	10	10	40	40	40	40
35	5	0	10	10	40	40	40	60
40	4	0	10	10	40	40	50	60

for문을 두 개 사용하여 바깥쪽 for문은 idx(현재 살펴보는 앱의 index),

안쪽 for문은 cst(현재 사용 가능한 비용)로 설정하여 dp에 값을 저장하면 된다

만약 cst보다 지불해야하는 비용이 더 크다면 이전 값을 그대로 사용한다

그렇지않다면 지불한 경우와 아닌 경우의 값 중에서 더 큰 값을 dp에 저장한다

이는 cst비용으로 지불 가능한 최대 값을 저장하는 배열이기 때문이다

또한, 현재 dp 배열에 저장된 값이 확보하고자하는 메모리 크기 이상이라면

더이상 더 큰 비용을 들이지 않아도 되므로 메모리 크기 이상을 만족하는 비용의 최솟값을 저장한다

다시 말해, 60의 비용을 지불해야할 때, 6의 비용을 지불하는 경우, 7의 비용을 지불하는 경우가 존재한다면

최종 답(result)에는 6을 저장하는 과정이다

import sys
input = sys.stdin.readline

num, memory = map(int, input().split())
App = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
dp = [[0] * (sum(cost)+1) for _ in range(num+1)]

result = sum(cost)
for idx in range(1, num+1):
    for cst in range(sum(cost)+1):
        if cst < cost[idx]:                 # cost가 충분하지 않은 경우
            dp[idx][cst] = dp[idx-1][cst]   # 그대로 값 유지
        else:                               # 값 갱신
            dp[idx][cst] = max(dp[idx-1][cst], App[idx] + dp[idx-1][cst-cost[idx]])
        if dp[idx][cst] >= memory:          # 필요한 메모리에 도달한 경우
            result = min(result, cst)       # 더 작은 값으로 갱신
            
print(result)

처음 코드를 작성할 때 for문에서 cst의 시작점을 1로 두었었는데, 틀렸습니다라는 문구가 등장하였다

그래서 찾아보다가 해당 반례를 통해 잘못된 부분을 찾을 수 있었다

5 60
30 10 20 35 40
0 1 0 0 0

해당 예시의 경우 0이 나와야하지만, for문의 cst 시작점을 1로 설정할 경우 1이 값으로 출력된다

지불해야하는 비용이 꼭 0이 아니어야한다는 조건이 없으므로 이를 고려하여 코드를 작성하여야한다