[백준 7579] 앱 - 배낭 문제, 다이나믹 프로그래밍

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

7579번: 앱

문제

우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.

하지만 스마트폰의 메모리는 제한적이기 때문에 한 번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다.

메모리 부족 상황에서 활성화되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다

현재 N개의 앱, A1,..., AN이 활성화되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화한 것을 ci라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화되어 있는 앱 A1,..., AN 중에서 몇 개를 비활성화하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그중에서 비활성화했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

 

 

---

배낭 문제 방식으로 풀 수 있다.

단, 내가 기존에 공부하던 배낭 문제와는 다르게 조금 신경 써야 할 부분이 있었다.

• 메모리 바이트 1~M을 행 또는 열로 두면 메모리 초과가 난다.
• M이내의 메모리가 아닌 M이상의 메모리를 얻어야 한다.

 

 

한번 메모리 초과로 실패를 겪은 후.. 앱 개수인 N의 크기의 행과 최대 비용 크기의 열을 두어 2차원 배열을 만들었다. j의 비용을 만들기 위한 최대 메모리 크기를 값으로 두었다.

 

 

전체를 탐색하면서

• 현재 앱의 비용이 현재 탐색 비용보다 비싸다면, 현재 앱의 메모리는 포함될 수 없다. 이전 값만 그대로 가져온다.
• 현재 앱의 비용이 현재 탐색 비용보다 비싸지 않다면, 이전 값과 (현재 앱의 메모리 크기+이전에서 모자란 금액에서의 메모리 크기) 중 더 메모리가 큰 것을 가져온다.

 

 

결과 dp의 모습은 다음과 같다.

마지막 행에서 메모리의 크기가 M이상일 때의 가장 첫 번째 인덱스값이 정답이 된다.

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]
[10, 10, 10, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40]
[10, 10, 10, 40, 40, 40, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60]
[10, 10, 10, 40, 40, 45, 60, 60, 75, 75, 75, 95, 95, 95, 95, 95]
[10, 10, 10, 40, 50, 50, 60, 80, 80, 85, 100, 100, 115, 115, 115, 135]

 

 

 

<< 전체 코드 >>

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
m = [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)]

for i in range(1, N+1):
    for cur in range(sum(c)+1):
        if c[i] > cur:
            dp[i][cur] = dp[i-1][cur]
        else:
            dp[i][cur] = max(dp[i-1][cur], dp[i-1][cur-c[i]]+m[i])

for j in range(sum(c)+1):
    if dp[N][j] >= M:
        print(j)
        break