백준 7579 앱

문제

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

코드

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
mlist = list(map(int, input().split()))
clist = list(map(int, input().split()))
sum_cost = sum(clist)+1
dp = [[0]*sum_cost for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(sum_cost):
        if clist[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(mlist[i-1]+dp[i-1][j-clist[i-1]], dp[i-1][j])

for i in range(sum_cost):
    if dp[-1][i] >= m:
        print(i)
        break

풀이

대표적인 dp 유형중 하나인 배낭 문제입니다

문제에서는 주어진 메모리를 확보하기 위한 최소한의 코스트를 출력하라고 되어있는데 내가 해당 코스트까지 사용할 수 있을 때 확보할 수 있는 가장 큰 메모리를 찾는식으로 해석을 하면 배낭 문제와 같은 풀이법으로 해결 할 수 있습니다

문제의 테스트 케이스를 예시로 dp 테이블을 만들어 보겠습니다

여기서 하늘색 영역이 dp테이블인데 dp[i][j]는 내가 j만큼의 코스트와 1~i인덱스까지의 메모리들을 사용할 수 있을때 가장 많이 확보할 수 있는 메모리값을 나타냅니다

점화식은

if clist[i-1] > j:
     dp[i][j] = dp[i-1][j]
else:
     dp[i][j] = max(mlist[i-1]+dp[i-1][j-clist[i-1]], dp[i-1][j])

이렇게 나오네요

dp의 가장 밑줄을 돌면서 제일 먼저 m보다 같거나 큰 값이 나오는 i값을 프린트해주면 됩니다