[골드 3] 백준 7579 - 앱 (파이썬)

분류 : 다이나믹 프로그래밍

링크 : https://www.acmicpc.net/problem/7579

풀이

메모리 확보를 위해서 필요한 최소 비용을 구하는 문제다.

앱 N개가 있고, 각각 메모리 m[i], 비용 c[i]를 가진다.

총 확보해야 할 메모리는 M보다 크거나 같으며, 비용의 합이 최소가 되도록 하는 앱을 선택한다.

DP 테이블은 다음과 같이 정의한다.

D = [[0] * 10001 for _ in range(N)]

D[i][j]는 i번 앱까지 고려했을 때, 비용 j 이하로 확보 가능한 최대 메모리를 나타내며, 비용 최대치가 10000이므로 열 크기를 10001로 설정한다.

# D[0][i] : 첫 번째 앱만 사용할 때의 최대 메모리
for i in range(c[0], 10001) :
    D[0][i] = m[0]

초기화는 첫 앱의 비용보다 크거나 같은 비용 i에 대해서 m[0]만큼 확보가 가능하다.

점화식은 다음과 같이 구성한다.

for i in range(1, N) :
    for j in range(10001) :
        D[i][j] = D[i - 1][j]  # i번째 앱을 쓰지 않았을 때

        if j >= c[i] :
            # i번째 앱을 사용하는 경우와 비교하여 더 큰 메모리 확보
            D[i][j] = max(D[i][j], m[i] + D[i - 1][j - c[i]])

i번째 앱을 사용하지 않는 경우는 이전 상태를 그대로 유지하고, i번째 앱을 사용하는 경우 이전상태에서 비용 c[i]를 줄이고, 메모리 m[i]를 추가한다.

마지막으로 최소 비용을 탐색한다.

for i in range(10001) :
    if D[N - 1][i] >= M :
        print(i)
        break

마지막 행에서 메모리 ≥ M을 만족하는 가장 작은 비용 i를 출력한다.

코드

# 백준 7579 - 앱
# 분류 : 다이나믹 프로그래밍

N, M = map(int, input().split())
m = list(map(int, input().split()))
c = list(map(int, input().split()))

D = [[0] * 10001 for _ in range(N)]

# D[0][i], i < c[0] -> 0, i >= c[0] -> m[0]
for i in range(c[0], 10001) :
    D[0][i] = m[0]

for i in range(1, N) :
    for j in range(10001) :
        D[i][j] = D[i - 1][j]

        if j >= c[i] :
            D[i][j] = max(D[i][j], m[i] + D[i - 1][j - c[i]])

for i in range(10001) :
    if D[N - 1][i] >= M :
        print(i)
        break