[🥇3 / 백준 7579 / 파이썬] 앱

 

7579번: 앱

문제

우리는 스마트폰을 사용하면서 여러 가지 앱(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 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다. 

 

예제 입력  5 60 30 10 20 35 40 3 0 3 5 4

예제 출력  6

 

풀이

 

냅색 문제와 유사한 문제이다.

 

최소한의 비용으로 목표치의 메모리를 획득하기 위해 비용을 점차 늘려가며

각 비용별로 획득할 수 있는 최대 메모리를 기록하는 방식으로 풀었다.

 

 

위에부터 차례대로 0~6 까지의 비용별로 메모이제이션 된 것을 나타낸다.

맨 왼쪽 라인은 계산 편의상 임의로 넣어둔 것이고, 두 번째 열부터 각각의 앱을 순서대로 나타낸다.

 

배열에 메모리를 할당하는 점화식은 다음과 같다.

 

max((사용할 수 있는 최대 비용 - 현재 앱의 비용)행의 직전 앱까지의 최대 메모리 + 현재 앱의 메모리, 바로 이전 앱까지의 메모리)

 

 

식으로 표현하자면 사용 가능한 최대 비용을 curCost, 현재 앱 순서를 i+1, 현재 앱의 비용을 cost, 현재 앱의 메모리를 memory라 한다면

 

dp[curCost][i+1] = max(dp[curCost - cost[i]][i] + memory[i],dp[curCost][i])

 

와 같이 된다. 설명이 너무 어려운 것 같으니 그림을 통해 알아보자.

 

이미 답이 위에 있지만, 네모칸에 들어갈 수를 구한다고 해보자.

 

네모칸의 열은 3번째 앱을 가르킨다. 즉, 비용 3의 메모리 20짜리 앱이다.

현재 사용할 수 있는 비용이 6이므로, 총 비용이 3일 때 기록했던 배열을 사용하자.

 

우리는 현재 3번째 앱까지 비활성화했을 때 최고 사용 가능 메모리가 얼마인지 알고 싶다.

즉, 2번째 앱 까지 이용했을 때의 메모리를 가져와야 한다. 이는 아래의 사진과 같다.

 

 

위 빨간 네모칸은 총 사용가능 비용이 3일 때, 그리고 1, 2번 앱을 가지고 적절한 조합을 만들 때 나올 수 있는 메모리이다.

여기에 3번째 앱을 더하면 비용은 총 3+3 = 6, 메모리는 40 + 20 = 60이 된다.

 

이번엔 마지막 칸의 메모리를 구해 보자.

7번째 행이므로 현재 사용 가능한 메모리는 6이 된다. (맨 첫번째 행은 메모리 0이다.)

그리고 5번째 앱의 비용은 4, 메모리는 40이다.

 

따라서, 비용을 6-4만큼 사용했을 때(3번째 행의) 4번 째 앱까지의 메모리 합산을 가져와 더하면 된다.

 

10 + 40 = 50이다. 

5번째 앱을 무조건 비활성화할 경우 50의 메모리까지만 얻을 수 있다는 뜻인데,

이런, 바로 왼쪽의 60보다 작은 수이다. 그렇다면 5번째 앱을 비활성화하지 않으면 된다.

 

즉, 그냥 바로 왼쪽의 숫자를 가져와 대입해주자.

 

최종적으로 마지막 행의 마지막 칸에 60의 메모리가 들어왔다.

우리가 구하려 했던 메모리가 60이므로, 더 이상 진행할 필요가 없다.

 

현재 사용 가능한 비용을 print하고 프로그램을 종료하면 된다.

 

n,m = map(int,input().split())
memory = list(map(int,input().split()))
cost = list(map(int,input().split()))

dp = [[0 for i in range(n+1)]]
curCost = -1

while(max(dp[curCost]) < m):
    # 배열이 얼마나 길어질 지 모르므로 계산때마다 추가해준다.
    dp.append([0 for i in range(n+1)])
    curCost += 1
    
    for i in range(n):
        if cost[i] <= curCost:
            dp[curCost][i+1] = max(dp[curCost - cost[i]][i] + memory[i],dp[curCost][i])
        else:
            dp[curCost][i+1] = dp[curCost][i]
print(curCost)