이번 문제는 다이나믹프로그래밍을 통해 해결하였다. 전형적인 0-1 배낭 문제로, 최소한의 비용으로 많은 메모리를 비워내는 것이 목표이다. dp리스트는 2차원으로 선언하였고, dp[i][j]에서 i는 현재 앱을 의미하고, j는 현재의 비용을 의미한다. dp안에는 해당 비용에서 비워낼 수 있는 최대한의 메모리량이 저장된다. 이 문제의 점화식은 다음과 같다.

dp[i][j] = max(memory[i] + dp[i-1][j-cost], dp[i-1][j])

이번 앱을 비활성화하기 전의 dp에 이번 앱의 메모리를 더한 값과 이번 앱을 비활성화하지 않은 바로 이전의 dp값 중 더 큰 값을 취하도록 하였다.

Code

n, m = map(int, input().split())
memory = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
total = sum(cost)
dp = [[0 for _ in range(total+1)] for _ in range(n+1)]
answer = 1e9
for i in range(1, n+1):
    for j in range(1, total+1):
        if j < cost[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(memory[i]+dp[i-1][j-cost[i]], dp[i-1][j])
        if dp[i][j] >= m:
            answer = min(answer, j)
if not m:
    print(0)
else:
    print(answer)