[백준] 7579번 : 앱

7579번: 앱

해당 문제는 다이나믹 프로그래밍 문제로 배낭문제와 비슷 합니다.

dp[i][j]는 메모리의 크기라고 하면 i는 Ai번째를 추가하는경우와 추가하지 않는 경우이며 j는 j의 비활성화의 가중치 값이다.

앱 Ai를 추가할때와 추가하지 않을때의 최대값을 구한다. 메모리가 빠르게 채워지면서 메모리가 M이상 채워 졌을때 j값의 최소값을 찾으면 된다.

아래는 예제 문제 1번을 테이블로 그려보았다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

dp = [[0 for _ in range(sum(C)+1)] for _ in range(N+1)]

ans = sum(C) + 1
for i in range(1, N+1):
    for j in range(1, sum(C)+1):
        if j >= C[i]: # 가중치가 더 클때만 넣을 수 있다.
            # 최대한 메모리를 크게 구해야 C의 가중치가 작게나온다.
            # 해당 앱이 있는경우와 없는경우
            dp[i][j] = max(dp[i-1][j-C[i]] + A[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

        if dp[i][j] >= M:
            ans = min(ans, j)

print(ans)