백준 7579 앱 - 파이썬

문제.

 

풀이.

냅색 알고리즘을 이용하는 문제이다.

우선dp 배열을 행은 켜진 app의 개수, 열은 cost들을 다 더한 값 만큼 생성해준다.

그리고 반복문으로 dp배열을 돌면서 다음과 같은 조건을 체크한다.

1) 현재 앱의 i번째 앱의 코스트가 j보다 크다면 끄지 못하므로 이전 행의 값을 가져온다.

 dp[i][j] = dp[i-1][j]

2) 현재 앱의 cost가 j보다 작거나 같을 경우 현재 앱을 껏을때의 메모리와 그렇지 않을 경우의 메모리 중 큰 값을 dp에 입력한다

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

 

3) 현재 dp[i][j[의 값이 M 이상이라면 현재 cost와 이전의 result 값을 비교해 더 작은 값을 저장한다.

 dp[i][j[ = min(result, j)

 

소스코드.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
memory = list(map(int, input().split()))
cost = list(map(int, input().split()))
dp = [[0 for i in range(sum(cost) + 1)] for j in range(N+1)]
result = sum(cost)


for i in range(1, N+1):
    m = memory[i-1]
    c = cost[i-1]

    for j in range(1, sum(cost) + 1):
        if j < c:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(m + dp[i-1][j-c], dp[i-1][j])

        if dp[i][j] >= M:
            result = min(result, j)
print(result if M != 0 else 0)