[ BOJ 7579 ] 앱(Python)

문제

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

M byte 이상의 메모리를 확보할 때, 소요되는 가장 적은 비용을 구하면 된다.

쥔챠,,. 냅색은 풀어도 풀어도 적응이 안된다.
내가 작성해놓은 코드를 보아도 매번 초면이다. 누구세요?

문제 풀이 (🔗 참고)

0. 입력 받기

n, m = map(int, input().rsplit())
memories = list(map(int, input().rsplit()))
cost = list(map(int, input().rsplit()))

tc = sum(cost)

1. dp 배열 정의하기

dp = [[0 for _ in range(tc+1)] for _ in range(n+1)]

dp[i][j] = i번째 앱까지 비용 j로, 얻을 수 있는 최대 메모리

2. cost[i]에 따라 dp 값을 할당,
구한 최대 메모리가 주어진 조건에 만족하는지 체크하기

for i in range(n):
    for j in range(tc):
        # cost[i]가 비용 j를 넘어가면 종료시킬 수 없으므로
        # 이전 값을 그대로 가져온다.
        if cost[i] > j:
            dp[i][j] = dp[i-1][j]
        # cost[i]가 비용 j보다 작거나 같으면 종료시킬 수 있다.
        # 앱을 종료시키지 않았을 때, 종료시켰을 때 가질 수 있는 최댓값을 비교해준다.
        else:
            dp[i][j] = max(dp[i-1][j], memories[i] + dp[i-1][j-cost[i]])

	# 구한 최대 메모리가 m을 만족시키는지 체크한다.
        if dp[i][j] >= m:
            result = min(result, j)

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().rsplit())
memories = list(map(int, input().rsplit()))
cost = list(map(int, input().rsplit()))

tc = sum(cost)
result = sys.maxsize

dp = [[0 for _ in range(tc+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(tc):
        if cost[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], memories[i] + dp[i-1][j-cost[i]])

        if dp[i][j] >= m:
            result = min(result, j)

if m==0:
    print(0)
elif n==1:
    print(cost[0])
elif result == sys.maxsize:
    print(n*m)
else:
    print(result)