백준 12865 파이썬 - 평범한 배낭 - 동적 계획법

백준 12865 파이썬

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

12865번: 평범한 배낭

이번 문제는 가방에 들어갈 수 있는 최대 무게가 정해져 있을 때 넣을 수 있는 물건의 최대 가치를 구하는 문제이다. 일단 최대값을 구하는 문제이기 때문에 가장 먼저 동적 계획법이 떠올랐습니다. 메모이제이션으로 사용할 값을 가방에 들어가는 무게를 중점으로 두고 물건을 확인할 때 가방의 최대 무게부터 물건의 무게까지 누적시키는 방법이 가장 먼저 떠올랐다.

 

 

Python 풀이 1

import sys
read = sys.stdin.readline

N, K = map(int, read().split())
cache = [0] * (K+1)

for _ in range(N):
    w, v = map(int, read().split())
    for j in range(K, w-1, -1):
        cache[j] = max(cache[j], cache[j-w] + v)
print(cache[-1])

가방 무게의 최대 값 K 부터 역순으로 들어갈 물건의 무게 w까지 순회하면서 해당 위치의 최대 가치(cache[j])와 들어갈 물건의 무게 w 만큼 이전의 최대 가치(cache[j-w])에 물건의 가치 v를 더한 값 중 최대값을 구한다.

 

 4가지 물건을 순차적으로 넣는다고 했을 때 캐시값의 흐름은 위와 같이 진행된다. 가방에 물건을 넣는거니까... 물건이 들어간 상태의 무게가 누적된다고 생각하면 쉽게 이해할 수 있다.

 

하지만 위 방법은 물건의 수와 상관없이 최대 무게 K에서 물건의 무게까지 매번 순회하기 때문에 꼭 필요하지 않는 시간복잡도가 생긴다. 만약 물건들 무게 합의 경우의 수만 순회한다고하면 훨씬 빠르게 처리할 수 있다. 이러한 경우 리스트보다는 딕셔너리를 사용하면 더 빠르게 처리할 수 있다.

 

 

Python 풀이 2

이 풀이는 가방 안에 들어가는 물건들 무게 합의 경우의 수를 기반으로 한 딕셔너리를 사용한다.

import sys
read = sys.stdin.readline

N, K = map(int, read().split())
cache = {0: 0}

for _ in range(N):
    curr_w, curr_v = map(int, read().split())
    temp = {}
    for w, v in cache.items():
        if curr_w + w <= K and curr_v + v > cache.get(curr_w + w, 0):
            temp[curr_w + w] = curr_v + v
    cache.update(temp)
print(max(cache.values()))

딕셔너리를 사용할 때 한가지 주의해야할 것이 있습니다. 딕셔너리를 순회할 때 딕셔너리를 수정하면 오류가 발생합니다. 그래서 임시로 사용할 딕셔너리를 만들어주고 update 함수를 이용해서 딕셔너리를 최신화 해주는 방법을 사용해야합니다.

 

풀이 1과 유사하지만 메모이제이션 캐시로 딕셔너리를 사용하고 현재의 물건 무게(curr_w)와 가방 안의 물건들 무게 합(w)이 최대 값 K보다 작거나 같고 해당 무게 합(curr_w + w)의 가치가 현재 물건 가치(curr_v) + 가방 안의 물건들 합의 가치(v) 적은 경우에 임시로 만든 딕셔너리에 포함 시킨다. 만약 해당 물건 합의 경우가 없는 경우 0과 더해서 해당 물건만 들어갈 수 있도록 하고 최종적으로 다 순회하면 cache 값을 update 합니다.

 

최종적으로 출력하는 값은 cache에 들어 있는 값 중 최대값 입니다.