백준 7579 - 앱 (파이썬)

Answer

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
memories = [0] + list(map(int, input().split()))
costs = [0] + list(map(int, input().split()))

sum_costs = sum(costs)
dp = [[0] * (sum_costs + 1) for _ in range(n + 2)]
result = sum_costs

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

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

if m != 0:
    print(result)
else:
    print(0)