#27 동적 계획법(Dynamic Programming) 2 - 심화(3)

 냅색(Knapsack) 알고리즘을 활용하여 해결할 수 있는 문제들을 알아본다.

 

1. 양팔저울(https://www.acmicpc.net/problem/2629)

 양팔저울과 무게추가 주어졌을 때, 각 구슬의 무게를 확인 가능한지 구하는 문제이다.  결국 양팔저울에 주어진 무게추를 올려 만들 수 있는 무게를 구하는 문제라고 볼 수 있다.

 

 냅색 문제를 풀때 사용했던 방식으로 동적 계획법을 적용하여 문제를 해결할 수 있다. 절차는 다음과 같다.

 

① 먼저 만들 수 있는 무게의 집합 s에 0을 넣고 시작한다.(아무것도 넣지 않은 경우) 

② 각 무게추마다 무게의 집합에 있는 만들 수 있는 무게들과의 합과 차를 집합에 추가한다. (중복값은 무시된다.)

③ 모든 무게추에 대해 ②의 작업이 끝나면 집합 s에는 주어진 무게추로 만들 수 있는 모든 무게가 들어있다.

④ 각 구슬에 대해 구슬의 무게가 집합 s에 들어있는지 확인하여 답을 반환한다.

 

이를 구현한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol2629():
    # 무게추의 갯수
    n = int(input())
    
    # 무게추의 무게 리스트
    weights = list(map(int, input().split()))
    
    # 구슬의 갯수
    m = int(input())
    
    # 구슬의 무게 리스트
    marbles = list(map(int, input().split()))

    # 만들 수 있는 무게 집합
    s = {0}
    
    # 각 무게추에 대해 해당 무게추가 추가되어 만들 수 있게되는 무게를 집합에 추가
    # set 자료구조의 특성상 중복값은 자동으로 무시된다.
    for w in weights:
        u = set()
        for v in s:
            u.add(v + w)
            u.add(abs(v - w))
        s |= u
        
    # 각 구슬의 무게를 무게추로 확인할 수 있는지 여부를 반환
    return ' '.join([('Y' if marble in s else 'N') for marble in marbles])

 

 

2.앱(https://www.acmicpc.net/problem/7579)

 실행 중인 n개의 앱(A1, A2, ... , An)은 각각 차지하는 메모리(m1, m2, ..., mn)와 종료에 드는 비용(c1, c2, ..., c3)을 가진다.  메모리를 M만큼 확보하기 위해 앱을 비활성화 시켜야할 경우, 필요한 최소 비용을 구하는 문제이다.

 

 말은 조금 바뀌었지만 결국 냅색 문제와 완전히 동일하다.  다만 주의할 점은 종료에 드는 비용은 그 범위가 1이상 100 이하로 작지만 앱이 차지하는 메모리의 크기는 1이상 10,000,000 이하로 굉장히 크다.  앱을 종료하여 메모리를 확보할 수 있는 경우의 수를 관리할 때, 메모리와 비용 어느것을 키 값으로 사용하더라도 문제는 해결할 수 있지만, 값의 범위를 생각하면 당연하게도 비용쪽을 키 값으로 해야 메모리/시간면에서 효율적인 코드가 될 것이다.  문제를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol7579():
    # 앱의 갯수 n,  확보해야할 메모리 크기 m
    n, m = map(int, input().split())
    
    # 각 앱이 차지하는 메모리 크기
    memory = list(map(int, input().split()))
    
    # 각 앱을 종료하는데 들어가는 비용
    cost = list(map(int, input().split()))
    
    # 앱을 종료하는데 드는 비용 총합 : 확보할 수 있는 메모리 총량
    dp = {0:0}
    
    # m 만큼의 메모리를 확보하기 위해 필요한 최소비용
    answer = float('inf')
    
    # 각 앱을 종료하는 것으로 확보할 수 있는 메모리 총량을 딕셔너리에 추가
    for app in range(n):
        u = {}
        for co, mem in dp.items():
            co += cost[app]
            mem += memory[app]
            if mem >= m:
                answer = min(answer, co)
            elif dp.get(co, 0) < mem:
                u[co] = mem
        dp.update(u)
        
    # 필요한 최소비용을 반환
    return answer

 

 

냅색 문제의 응용 문제들은 제법 자주 등장한다.  방법만 알고있다면 어렵지 않게 풀 수 있는 유형이니 잘 알아두고 넘어가도록 하자.