알고리즘 스터디 - 백준 7579번 : 앱

문제 해석

• "비활성화" : 새로운 앱을 실행시킬 때 메모리가 부족해지면 운영체제에서 다른 앱 메모리를 삭제하는 것
• "비활성화"의 단점 : 비활성화된 앱을 재실행할 경우 시간이 더 필요함
• N개의 앱 A1, ..., AN은 각각 m1, ..., mN의 메모리를 사용하고 재실행의 경우는 c1, ..., cN의 비용이 들어감

목적 : M 바이트의 메모리가 필요한 앱 B를 새로 실행할 때 A의 앱을 비활성화하고 실행하는 비용 c의 합을 최소화하는 방법을 찾기

입력

1. N, M : 앱 개수, B의 메모리 크기
2. m1, ..., mN : 각 앱의 메모리 크기
3. c1, ..., cN : 각 앱의 비활성화 비용

어떤 알고리즘을 사용해야할까?

1. 무작위 M을 생성하고 최소 비용의 경우의 수를 구함 - 브루트포스
2. 메모리 크기가 높은 순으로 먼저 골라서 넣음 - 그리디
3. 배낭 문제를 적용함 - 다이나믹 프로그래밍

배낭문제

한 여행자가 여행을 하러 갈때 배낭에 담을 수 있는 무게의 최댓값이 있고 배낭에 넣을 수 있는 짐에는 각각 무게와 가치가 있을 때 배낭 무게를 최대로 하면서 가치의 합이 최대가 되도록 하는 문제

import sys

# W: 배낭의 무게한도, wt: 각 보석의 무게, val: 각 보석의 가격, n: 보석의 수
def knapsack(W, wt, val, n):  
    # DP를 위한 2차원 리스트 초기화
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        # 각 칸을 돌면서
        for w in range(W+1):  
            # 0번째 행/열은 0으로 세팅
            if i==0 or w==0:  
                K[i][w] = 0
            # 점화식을 그대로 프로그램으로
            elif wt[i-1] <= w:  
                K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])  
            # max 함수 사용하여 큰 것 선택
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]

wt = []
val = []
N, K = map(int, sys.stdin.readline().strip().split())
for i in range(N):
    w, v = map(int, sys.stdin.readline().strip().split())
    wt.append(w)
    val.append(v)

print(knapsack(K, wt, val, N))

최종 알고리즘 코드

• 기존 배낭 문제는 무게를 기준으로 dp를 만들었지만 여기서는 cost를 기준으로 dp를 만든다.

조건

1. cost[i] > j : cost가 부족해 앱 비활성화가 불가능
2. 그렇지 않으면 dp와 최대 메모리 값을 더함
3. 확보한 메모리 값이 M을 넘기면 비용을 더 작은 걸로 갱신함

import sys

N, M = map(int, sys.stdin.readline().split())
memory = list(map(int, sys.stdin.readline().split()))
cost = list(map(int, sys.stdin.readline().split()))
max_cost = sum(cost)

def app(n, m, mem, co):
    global max_cost
    dp = [[0 for _ in range(sum(co)+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(len(dp[0])):
            if co[i] > j: 
                dp[i][j] = dp[i - 1][j] 
            else: 
                dp[i][j] = max(dp[i - 1][j - co[i]] + mem[i], dp[i - 1][j]) 
            
            if dp[i][j] >= m:
                max_cost = min(max_cost, j)
    
    return max_cost

print(app(N, M, memory, cost))