12865:평범한 배낭 [백준 문제풀이][Python][CLASS 4]

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

정석적인 dp 문제이나... 이해하는데 꽤나 애를 먹었다. 다음 문제를 위해 정리해서 글을 끄적여본다.

아이디어1

우선 처음에는 이중 for문을 돌면서 리스트에다가 가능한 모든 조합을 넣어서 max 값을 뽑아냈다.(난 이게 완전 탐색인지도 몰랐다)

 

시도1

from collections import deque
n,k=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i] = map(int,input().split())
d=deque()
c=0
for i in range(n):
    d.append((w[i],v[i]))
    for j in range(0,len(d)-1):
        if d[j][0]+w[i]<=k:
            d.append((d[j][0]+w[i],d[j][1]+v[i]))
            if(d[-1][1]>c):c=d[-1][1]
print(c)

실패한 이유

당연히 결과는 시간초과. 첫번째 for문은 n번 반복하고 2번째 for문은 d의 길이만큼 반복하는데, 최악의 경우 d가 2^n 까지 커질 수 있으므로 시간복잡도는 O(n*2^n)이 된다. n의 범위가 100이하이므로 최적화가 필요하다.

 

아이디어2

두 번째로는 dp를 이용한 풀이를 해보았다. 요약해서 얘기를 하면 0~7까지의 최대 무게를 담을 수 있는 리스트 l에다가 짐이 들어올때마다 그 무게가 들어올 수 있는 범위를 탐색해서 최댓값으로 업데이트 해주는 건데... 말로 하면 어려우니 그림으로 보여주겠다.

w=6인 짐이 들어왔을땐 0+6,1+7의 조합이 가능하므로 6~7까지만 업데이트 해준다. 이로써 1번 코드에 비해 불필요한 검증을 줄일 수 있다. 또한 1번 코드를 짤 때 걱정했던 것중 하나는 굳이 k의 무게를 맞추지 않아도 최댓값이 나와버리는 상황을 고려한거였는데, 가능한 모든 조합을 업데이트 함으로써 이러한 문제를 해결했다. 

정답 코드

n, k = map(int, input().split())
l=[0]*(k+1)
for i in range(n):
    w,v = map(int,input().split())
    for j in range(k,w-1,-1):
        l[j] = max(l[j],l[j-w]+v)#최댓값으로 업데이트
print(l[k])

 

2번을 짜고 다시 생각해보니 1번 코드를 튜플 형태로 저장하지 말고 두개의 리스트로 나눠 저장한다음, 겹치는 무게가 있을때 최댓값만 남도록 업데이트 하면 다른 존재할 수 없는 무게의 조합에 대한 업데이트가 줄어드니 2번 코드보다 시간 복잡도가 줄어들수도 있을거 같다. 더 복잡한 dp문제가 나오면 시도해봐야겠다.