[BOJ] 앱

---

코드

import sys
input = sys.stdin.readline

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

dp = [[0]*(tc) for _ in range(N)]

result = 10e9

# dp[i][j] = i개의 앱에서 비용 j로 얻을 수 있는 최대 메모리
for i in range(N):
    for j in range(tc+1):
        # 현재 앱의 종료비용이 j보다 크면 종료시킬 수 없으므로 이전 값을 쓴다.
        if c[i] > j:
            dp[i][j] = dp[i-1][j]
        # 현재 앱의 종료비용이 j보다 작거나 같으면
        # 앱을 종료시키지 않을 때 얻을 수 있는 최대메모리와
        # 앱을 종료시킬 때 얻을 수 있는 최대메모리를 비교하여 큰 것을 저장한다.
        else:
            dp[i][j] = max(dp[i-1][j], m[i] + dp[i-1][j-c[i]])

	   # M을 만족시키는 경우 현재까지의 최소값이면 갱신한다.
        if dp[i][j] >= M:
            result = min(result, j)

print(result)

결과

풀이 방법

• 배낭문제 알고리즘 문제이다.
• DP[i][j] = i개의 앱에서 비용 j로 얻을 수 있는 최대 메모리 로 설정하고 푸는 문제이다.

---