백준 | [파이썬 Python] 7579 앱

 

---

문제

 

 

코드

def min_cost_to_free_memory(N, M, memories, costs):
    max_cost = sum(costs)
    dp = [0] * (max_cost + 1)
    
    for i in range(N):
        memory = memories[i]
        cost = costs[i]
        
        for j in range(max_cost, cost -1, -1):
            dp[j] = max(dp[j], dp[j-cost] + memory)
        
    for k in range(max_cost + 1):
        if dp[k] >= M:
            return k
    return -1

N,M = map(int, input().split())
memories = list(map(int, input().split()))
costs = list(map(int, input().split()))
print(min_cost_to_free_memory(N,M,memories,costs))

 

 

설명

복잡해 보이는데 이해하면 쉬운 문제이다.

문제에서 구해야 하는 것은 사용 가능한 메모리

위 메모리를 찾기 위해 유지비용(?)을 dp에 요리조리 잘 요리하면 된다.

역순으로 하는 이유는 이 전 dp 값을 참조 할 때 현재 메모리가 더해진 값을 사용하는 것을 방지하기 위함이다

 

 

 

예시