[CLASS 4]백준 12865번 - 평범한 배낭

12865번 : 평범한 배낭

 

DP중에서도 대표적인 냅색(Knapsack,배낭) 문제이다. 처음 푼다면 좀 어지러울 수 있는데, 물품을 하나씩 검사하면서 최대 가치를 갱신한다는 점에서 정말 DP스러운 문제라고 생각한다.

 

내 코드(1차):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n, k = map(int,input().split())
l = [0]
for _ in range(n):
    w, v = map(int,input().split())
    # 버틸 수 있는 무게를 넘는 물건은 추가하지 않음
    if w <= k:
        l.append((w,v))

n = len(l) - 1
# dp[a][b] -> a만큼 버틸수 있는 가방에 b번째 물건까지 넣었을 때 최대가치
dp = [[0]*(n+1) for _ in range(k+1)]
for w in range(1,k+1):
    for i in range(1,n+1):
        # 가방에 넣어도 최대무게를 넘지 않는다면
        if w-l[i][0] >= 0:
            # 해당 물건을 넣지 않았을 때와 넣었을 때 중 작지 않은 값 대입
            dp[w][i] = max(dp[w][i-1],dp[w-l[i][0]][i-1] + l[i][1])
        else:
            # 최대무게를 넘는다면 넣지 않은 값 대입
            dp[w][i] = dp[w][i-1]

print(dp[k][n])

 

1차적으로는 2중 리스트를 사용하여 풀었다. 그러나 파이썬 시간 제한(8초)에 아슬아슬하게 걸쳐서 통과했다. (7828ms) 그래서 시간을 어떻게 하면 개선할 수 있을까 생각하면서 다른 분들의 코드를 보고 1중 리스트로도 풀 수 있다는 점을 깨달았다.

 

내 코드(2차):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n, k = map(int,input().split())
dp = [0]*(k+1)
for _ in range(n):
    w, v = map(int,input().split())
    for j in range(k,0,-1):
        if j >= w:
            dp[j] = max(dp[j],dp[j-w]+v)

print(dp[k])

 

1중 리스트로 풀 때는 리스트의 인덱스 j가 최대무게를 뜻한다. 물품을 하나씩 받으면서 j를 k부터 0까지 돌리면서 리스트를 갱신해주면 된다. 이렇게 하고 제출하니 시간이 거의 반으로 줄었다. (4160ms)