[백준 7579번] 앱 (Python3)

import sys
input = sys.stdin.readline
INF = 10**9

N,M = map(int,input().split())

memory = list(map(int,input().split()))
cost = list(map(int,input().split()))

sumcost = sum(cost)
DP = [[0]*(sumcost+1) for i in range(N+1)]

result = sumcost
for n in range(1,N+1):
  for c in range(1,sumcost+1):
    m1 = memory[n-1]
    c1 = cost[n-1]
    DP[n][c] = DP[n-1][c]
    if c-c1 >= 0:
      DP[n][c] = max(DP[n][c],DP[n-1][c-c1]+m1)
    if DP[n][c]>=M:
      result = min(result,c)

print(result)

기본적인 냅색문제

 

평범한 배낭 문제를 풀지 않았더라면 아주 어려웠겠지만, 냅색을 이미 한번 활용해본 상황에서는 식은죽 먹기...

라고 했지만 사실 살짝 애먹었다.

N에 대한 for문을 먼저 돌아야 하는데 착각해서 C에 대한 for문을 먼저 돌리고, for문 범위에 +1 안해줘서 틀리고...

 

 

오늘의 교훈) 실수하지 말자!