📱 앱

01 Aug 2022 in Algorithm on Knapsack

백준 Gold3

앱

문제

---

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

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

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

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

입력

---

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, …, AN이 사용 중인 메모리의 바이트 수인 m1, …, mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, …, cN을 의미한다

단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, …, mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, …, cN ≤ 100이고, M ≤ m1 + m2 + … + mN이다.

출력

---

필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.

예제 입력 1

5 60
30 10 20 35 40
3 0 3 5 4

예제 출력 1

6

📖 가져다 쓰기

처음에는 투포인터를 떠올렸다. cost0부터 cost n-1까지 검사를 해보면서 확보할 메모리가 존재한다면 해당 비용들의 합을 return해주면 될 것이고 확보할 메모리가 없다면 이를 1 바이트 증가시켜서 재탐색을 한다.

그러나 이 문제에서의 비용은 부분 연속 수열이 아니다. 다시 말해, index를 무작위로 선정해서 합해도 되므로 투포인터를 활용하기에는 적절치 않다.

알고리즘 분류상 이 문제는 배낭 문제로 분류되어 있다. 배낭 문제가 무엇일까?

Knapsack Algorithm

냅색 알고리즘이라고도 불리는 배낭 문제는 도둑이 배낭에 여러 개의 짐을 훔쳐서 달아나려고 하는데 배낭에 넣을 수 있는 무게는 한정적이기에 최대한 가치가 높은 것을 담아가려고 하는 문제이다.

언뜻 보면 그리디 알고리즘과 비슷해보이지만 차이점이 무엇일까? 🧐

다음 질문에 답을 해보자. ㅎㅎ

배낭 = 무게 한계 15kg
A = 가치 10 , 무게 13kg
B = 가치 6, 무게 6kg
C = 가치 5, 무게 6kg

배낭을 최대한 가치가 높게 싸려고 하는데 이를 그리디하게 접근하면 A를 담고 끝이 난다.

그러나 정답은 B와 C를 담아 가치 11의 배낭이 최대 가치이다.

이를 위하여 냅색 알고리즘이 존재하고 이는 Dynamic Programming으로 구현한다!

이처럼 물건을 나눌 수 없는 경우를 [0-1 냅색 알고리즘]이라고 칭한다.

반면에 물건을 나눌 수 있는 경우는 어떻게 될까? [Fraction 냅색 알고리즘]은 그리디로도 해결이 가능하다.

위와 같이 물건의 가치를 무게로 나누어 단가를 맞춘 다음, 최대한 이득을 보는 단가로 계속 챙겨주면 되기 때문이다.

이 문제를 [0-1 냅색 알고리즘]으로 분류할 수 있는 이유는 다음과 같은 특징 때문이다.

• 배낭 👉🏻 확보해야 하는 메모리
• 짐의 무게 👉🏻 앱의 메모리
• 가치 👉🏻 비용
• 앱 👉🏻 나누어질 수 없음

📐 과정 설계/관리

최종 DP 테이블은 위와 같은데 중요 부분인 빨간 박스를 주목하자.

현재 위치는 메모리가 20인 3번 앱에 위치해있고 3번 앱의 비용은 3이다.

그리고 비용이 0부터 15까지(모든 앱을 다 껐을 때 비용이 15이니까) 각각의 경우의 확보할 수 있는 최대 메모리이다.

이러한 상황에서 다음 4번 앱으로 넘어가려고 한다.

메모리는 35바이트이고 비용은 5다. 동일하게 비용이 0부터 15까지 모든 경우의 확보 메모리를 구할건데

0~4까지는 이전 dp배열과 동일하게 처리해주면 된다. 왜냐하면 어차피 4번앱을 끄면 5의 비용이 소모되는데 0~4 비용으로는 만족시키지 못하기 때문이다.

비용 5 이상부터는 4번앱을 껐을때와 아닐 때로 구분하여 최대 확보 메모리를 갱신해주면 된다.

👨🏻‍💻 CODE

import sys
input = sys.stdin.readline

N, necessity = map(int,input().split())
memory = [0] + list(map(int,input().split()))
cost = [0] + list(map(int,input().split()))

# dp[i][j]: i번째의 앱 & j 비용으로 최대 확보 메모리
dp = [[0]*(sum(cost)+1) for _ in range(len(cost))]

minimum = sum(cost)
for i in range(1,len(cost)):
    for j in range(sum(cost)+1):

        if cost[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],memory[i]+dp[i-1][j-cost[i]])
        
        
        if dp[i][j] >= necessity:
            minimum = min(minimum,j)
        

print(minimum)