Baekjoon 7579. 앱 / Python

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

알고리즘 설명

문제 설명

앱을 비활성화하기 위한 최소 비용으로 메모리를 확보해야한다.
DP를 활용하여 풀이했다.

코드 설명

dp[i][j] : i번째 앱까지 고려했을 때, j의 비용으로 확보할 수 있는 최대 메모리
필요한 메모리를 확보했을 경우 최소 비용을 갱신

import sys
input = sys.stdin.readline

# 입력
n, m = map(int, input().split())
memories = [0] + list(map(int, input().split()))  # 앱들이 사용하는 메모리
costs = [0] + list(map(int, input().split()))  # 앱들을 비활성화하는 비용

# DP 테이블 초기화
# dp[i][j]: i번째 앱까지 고려했을 때 j 비용으로 확보할 수 있는 최대 메모리
# 비용의 최대값은 모든 비용의 합으로 초기화
max_cost = sum(costs)
dp = [[0] * (max_cost + 1) for _ in range(n + 1)]

# 결과값 초기화
res = max_cost

# 다이나믹 프로그래밍 수행
for i in range(1, n + 1):
    for cost in range(max_cost + 1):
        now_memory = memories[i]
        now_cost = costs[i]
        if cost < now_cost:
            dp[i][cost] = dp[i - 1][cost]  # 현재 앱을 비활성화하지 않는 경우
        else:
            dp[i][cost] = max(dp[i - 1][cost], dp[i - 1][cost - now_cost] + now_memory)  # 앱 비활성화 여부 선택
        
        # 필요한 메모리 확보 조건을 만족하는 경우 최소 비용 갱신
        if dp[i][cost] >= m:
            res = min(res, cost)

# 결과 출력
print(res)