[백준/python]7579번 앱 - knapsack, dp
냅색 알고리즘에 해당 되는 문제이다. 냅색 알고리즘에는 가방에 보석을 담을 때 보석을 자를 수 없다고 가정하는 0-1 냅색 알고리즘과 자를 수 있다고 가정하는 Fractional 냅색 알고리즘이 있다.
이 문제는 0-1 냅색 알고리즘에 해당되는 문제다. 앱을 종료했을 때 최소한의 비용으로 최대한 M바이트 이상을 확보해야 한다. DP를 사용하여 앱을 종료했을 때 확보할 수 있는 바이트를 탐색해나가면 된다.
냅색 알고리즘 설계하기
냅색 문제를 푸는 것이 처음이었기 때문에 단순히 dp로 풀어야 겠다는 생각만 있었다. 문제를 풀 때 2차원 배열이 필요할 것이라는 생각은 쉽게했다. 하지만 dp[i][j]에서 i는 앱의 개수만큼 인덱스를 늘려가며 탐색을 하면 된다고 생각했는데 j를 어떤 변수로 표현해야될 지 감이 안왔다.
-
처음에는 i번째 앱까지 최대 j바이트를 확보했을 때 최소 비용을 dp[i][j]에 저장해야겠다고 생각했다.
dp[i][j] = min(dp[i-1][j-byte] + cost , dp[i-1][j])i번째 앱까지 사용했을 때 j바이트를 확보하며 사용한 최소 비용을
- i-1번째 앱까지 사용했을 때 j-byte만큼 확보하며 사용한 최소 비용 + i번째 앱의 비용
- i-1번째 앱까지 사용했을 때 j바이트 만큼 확보하며 사용한 최소 비용
둘 중 작은 값으로 갱신한다. 모든 앱에서 j가 1씩 증가하며 반복문을 실행한다. j=1,2,3,,확보할 수 있는 최대 바이트까지 모든 경우를 탐색한다. 주어진 조건에 의해 M은 최대 10,000,000이다. 반복문을 이만큼 실행하는 것은 비효율적이므로 다른 방법을 사용해야 한다.
-
i번째 앱깨지 최대 j 코스트로 확보할 수 있는 최대 바이트를 갱신하며 저장한다.
dp[i][j] = max(dp[i-1][j-cost] + byte, dp[i-1][j]i번째 앱까지 사용했을 때 j 비용을 사용해서 확보할 수 있는 최대 바이트를
- i-1번째 앱까지 사용했을 때 j-cost 만큼의 비용을 사용해서 확보할 수 있는 최대 바이트 (i번째 cost가 현재 j 보다 클 때만 비교 가능) + i번째 앱을 사용해서 확보할 수 있는 바이트
- i-1번째 앱까지 사용했을 때 j 비용을 사용해서 확보할 수 있는 최대 바이트
둘 중 큰 값으로 갱신한다. 모든 앱에서 j가 1씩 증가하며 반복문을 실행한다. j=1,2,3,,,최대 비용까지 모든 경우에서 확보할 수 있는 최대 바이트를 갱신한다. 이 때 최대 비용은 주어진 조건에 따라 100*100을 넘지 않는다.
예를 들어, i번째 앱의 cost가 10이라면 j=1~10까지 dp[i][j]는 모두 dp[i-1][j]가 된다. 만약 이 경우에서 i=1(첫번째 앱)이라면 확보할 수 있는 바이트가 0이 되는 것이다.
모든 dp를 갱신하며 M바이트 이상 확보할 수 있는 경우 가장 작은 비용을 출력하면 된다.
코드
N, M = map(int, input().split())
memory = [0]+list( map(int, input().split()) ) #빈 배열 넣어주는 것 유의
cost = [0]+list(map(int, input().split()))
result = sum(cost)+1
dp = [ [0 for _ in range(sum(cost)+1)] for _ in range(N+1)]
for i in range(1, N+1) :
m = memory[i]
c = cost[i]
for j in range(1, sum(cost)+1) :
if j < c :
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j-c] + m, dp[i-1][j])
if dp[i][j] >= M :
result = min(result, j)
print(result)
댓글남기기