[백준/7579/파이썬] 앱

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

7579번: 앱

Problem

• 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.
• 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다.
• 여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

 

조건

• 현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자.
• 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자.
• 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 
• 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다

SOL

0 -1 배낭 문제의 응용버전이다.

이 문제는 배낭의 크기 (넣을 수있는 최대크기)에 따라서, 가치를 max로 하는게 아니고, 메모리 공간이 M이 넘는 상황에서, Cost가 최소가 되게끔 앱을 비활성화 시키는 문제이다. cost에 따라서, 남길 수 있는 최대 byte수를 기록해주는 DP table을 생성할거다.

 

따라서, Cost를 기준으로, Byte가 M이 넘는다면, 그 Cost 중에서 최소를 계속 갱신 하는 형태의 0-1배낭을 구현해야한다. 그리고, 같은 코스트라면, Byte를 크게(여유 메모리공간)을 넉넉하게 남기는게 이득이다! 따라서, cost에 따른 byte를 저장해줄거다.

 

• P[i][w] = i번째 앱 까지, W(cost)에 따라서 얻을 수 있는 여유 메모리 공간의 최댓값을 저장하는 2차원 배열.
  • if) W<Cost: P[i][W] = P[i-1][W]
  • else if) W>=Cost: P[i][W] = max(P[i-1][W],P[i-1][W-Cost]+Byte)
• Cost = i번째 앱을 비활성화 시키기 위한 Cost(C[i])
• Byte = i번째 앱을 비활성화 시키면, 얻을 수 있는 여유 메모리 공간 (A[i])

1. if 앱을 비활성화 시키기 위한 Cost가 충분하지 않다면(Cost>W), 현재 앱은 활성화 시킨체로 냅둔다. ( 이전 상태에서는 이미, 최대 byte가 저장되어있기 때문에, 이전 상태를 불러온다고 생각해도 된다.)
2. 앱을 비활성화 시키기 위한 Cost가 충분하다면 ,(W>Cost) 현재 앱을 활성화 시킨체로 냅둘지, 현재 앱을 비활성화 시키는 선택을 할지 정한다.( 현재 앱을 비활성화 시킨다면, Cost가 들기 때문에, 그 이전 상태에서 W-cost를 불러와야한다)

import sys
input= sys.stdin.readline

N,M=map(int,input().split())

Mem=[0]+list(map(int,input().split()))
C=[0]+list(map(int,input().split()))
ans=sys.maxsize

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

for i in range(1,N+1):
    byte=Mem[i]
    cost=C[i]
    for j in range(1,sum(C)+1):
        #현재 앱을 비활성화 시킬만큼, cost가 충분하지 않은 경우
        if j<cost:
            DP[i][j]=DP[i-1][j]
        else:
            #현재 코스트가 충분한 경우는 , 2가지 경우가 있을수 있다.
            DP[i][j]= max(DP[i-1][j],DP[i-1][j-cost]+byte)
        if DP[i][j]>=M:
            ans=min(ans,j)
#for d in DP:
    #print(d)
print(ans)