백준 7579 앱

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

배낭문제와 비슷한 문제이다.
배낭문제에선 현재 선택한 물건을 넣는다와 안넣는다로 선택할 수 있는데,
현재 선택한 물건을 넣는 경우에 비교해야 할 부분은
"가방의 무게에서 현재무게를 뺐을때의 가치의 최상값 + 현재 물건의 가치 : 현재 물건을 넣지 않았을때의 가치의 최상값"을 비교했었다.
이때 dp를 이용해 가치의 최상값들을 계속 저장했었는데, 행에는 보석의 번호와 열에는 보석의 무게를 담았었다.
근데 이 문제에서는 무게가 최대 천만이기 때문에 배낭문제와 같이 dp를 구성하면 메모리가 부족함이 자명했다.

그렇기 때문에 위의 문제에서는 행에서는 메모리 번호, 열에서는 비용의 크기로 구성해 dp를 만들면 된다.
메모리 크기가 최대 100이니 100까지 순회를 하면서
현재 메모리보다 작은 idx에선 이전 dp의 최댓값을 그대로 가져오면 되고,
현재 메모리보다 큰 idx에선 현재 메모리를 선택할지 안할지의 상황에서 두가지를 고려하면 되는데,
현재 메모리를 선택하지 않았을때의 값(dp[i-1][j])과 (현재 메모리를 선택했을때 현재 메모리의 비용만큼 뺏을때의 최대 메모리 + 현재 메모리) dp[i-1]j-costs[i]]+memory[i] 를 비교해주면 된다.

정답을 찾을때는 M보다 큰 dp값을 찾았다면 현재 j인덱스를 저장해 놓는다.

순회를 할때, 메모리의 순서에는 영향이 없으니 그냥 i-1을 써도 무방하다.

n,m = map(int,input().split())
memory = list(map(int,input().split()))
costs = list(map(int,input().split()))
max_cost = sum(costs)
dp = [[0]*10100 for i in range(101)]
ans = sum(costs)
for i in range(n):
    for j in range(max_cost+1):
        if costs[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-costs[i-1]] + memory[i-1])
        if dp[i][j] >= m:
            ans = min(ans,j)
print(ans)