[python] 백준 7579 앱

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

7579번: 앱

 

 

문제 해결

• 용량 M을 줄여야하는데 $A_{i}$ 바이트와 줄이는데 비용 $C_{i}$가 주어졌다. 이 때 최소비용을 구하는 문제
• 이는 배낭 문제라고 한다.
• https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C
   
• dp[i][j]를 i번째 물건까지 봤을 때 j요금 이하로 만들 수 있는 줄일 수 있는 메모리 합을 이야기한다.
• j가 i번째 메모리 사용할 때 비용($C_{i}$)보다 작다면 $i$번째 메모리를 사용할 수 없다는 뜻이므로 dp[i][j] = dp[i-1][j]와 같다.
• j가 i번째 메모리 사용할 때 비용보다 크다면 $i$번째 메모리를 사용할 수 있다는 뜻이다. 그러면 dp[i][j] = max($A[i]$+dp[i-1][j-C[i]], dp[i-1][j])와 같다.

배낭 문제 - 나무위키

 

 

CODE

import sys
input = sys.stdin.readline



def main():
    result = sum(C)
    for i in range(1,N+1):
        byte = A[i]
        cost = C[i]
        
        for j in range(sum(C)+1):
            if j<cost:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(byte+dp[i-1][j-cost], dp[i-1][j])
            
            if dp[i][j] >=M:
                result = min(result, j)
    if M != 0:
        print(result)
    else:
        print(0)
        
if __name__=='__main__':
    N, M = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    C = [0] + list(map(int, input().split()))
    dp = [[0 for _ in range(sum(C)+1)] for _ in range(N+1)]
    
    main()