[BOJ/Python] 12865. 평범한 배낭

📌 문제

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

12865번: 평범한 배낭

 

📌 문제 접근 방법

1. 처음에는 가치가 큰 물건 별로 우선적으로 배낭에 넣는 방식으로 구현해보았으나 시간초과!
2. 결국 구글링을 해보니 Knapsack Algorithm을 사용해야 하는 것이었다.
   

   

   
   
   • 인덱스 에러가 나지 않도록 0번째 줄을 포함해서 2차원 배열을 생성한다.
   • i 번째 물건을 가방에 넣었을 때 / 넣지 않았을 때의 최대 가치를 계산해서 표를 채워준다.
   • 위의 로직을 코드로 구현한다.

 

📌 코드

import sys

N, K = map(int, sys.stdin.readline().split())

# 가로축 : 무게 (0~K) / 세로축 : 개수 (0~N)
# 그 전값과 비교할 때 첫 번째 값도 비교를 해주기 위해서 0번 인덱스도 생성
bag = [[0 for _ in range(K+1)] for _ in range(N+1)]
things = [[0, 0]]  # (무게, 가치)

for _ in range(N):
    things.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N+1):
    for j in range(1, K+1):
        weight = things[i][0]
        value = things[i][1]

        if j < weight:
            # 물건을 가방에 넣어줄 수 없음 
            # -> 물건을 가방에 넣기 바로 이전의 상태 그대로 가져오기
            bag[i][j] = bag[i-1][j]
        else:
            # 물건을 가방에 넣어줄 수 있음
            # -> 물건을 가방에 넣은 전/후의 가치를 비교해서 더 큰 가치값으로 채우기
            before = bag[i-1][j]
            after = value + bag[i-1][j-weight]

            bag[i][j] = max(before, after)

print(bag[N][K])