[백준][Python] 7579번 앱 - 코팩

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

7579번: 앱

풀이

배낭 알고리즘을 이용해서 풀어줄 수 있는 문제이다. solved.ac 기준으로 class5를 달성하기 위해서 거쳐가야하는 문제 중 하나이다.

참고로 배낭 알고리즘은 Dp 알고리즘이기에 이 문제를 풀기 이전에 간단한 Dp문제를 풀고 오기를 바란다.

 

이 문제는 새로운 B앱을 활성화하기 위해 M메모리만큼 비활성화해야하는 앱들의 집합의 cost 최솟값을 찾는 문제이다.

따라서 기존의 배낭 알고리즘 문제에서 무게가 이 문제에서는 cost라고 보면된다.

 

배낭 채우기 알고리즘:

https://sunghyun98.tistory.com/265

[알고리즘] 배낭 채우기 알고리즘(Knapsack Problem)

 

코드

# 7579번 앱
n, m = map(int, input().split())
app_memory = [0] + list(map(int, input().split()))
app_cost = [0] + list(map(int, input().split()))
dp = [[0] * (sum(app_cost)+1) for _ in range(n+1)]
INF = float("inf")
ans = INF

for i in range(1, n+1):
    v = app_memory[i]
    w = app_cost[i]
    for j in range(1, sum(app_cost)+1):
        if w > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

        if dp[i][j] >= m:
            ans = min(ans, j)
if ans == INF:
    print(0)
else:
    print(ans)

 

출력결과