[BOJ] 12865 : 평범한 배낭 [다이나믹 프로그래밍](Python)

문제 링크

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

12865번: 평범한 배낭

소스 코드

import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
bag = [[0 for _ in range(k+1)] for _ in range(n+1)]

items = [(0,0)]
for i in range(n):
    w,v = map(int,sys.stdin.readline().rstrip().split())
    items.append((w,v)) # weight,value

for row in range(1,n+1):
    for col in range(1,k+1):
        weight = items[row][0] # 넣으려는 아이템의 무게
        value = items[row][1] # 넣으려는 아이템의 가치

        if col < weight: # col:현재 가방에 담을 수 있는 최대 무게
            bag[row][col] = bag[row-1][col] # 직전의 가방 무게를 그대로 가져온다
        else: # 현재 아이템을 넣는 경우 or 현재 아이템을 담지 않는 경우 중 큰 값을 가져온다
            bag[row][col] = max(bag[row-1][col],bag[row-1][col-weight]+value)

print(bag[n][k])

 

해설

• 다이나믹 프로그래밍, DP
• 상향식, Bottom-up

처음 봤을 때는 당연히 DP 유형이라고 생각했는데 아이디어가 바로 떠오르지 않았습니다 ㅜㅜ

그래서 Brute Foce 방식으로 푸는 건가..? 했는데 사실 그렇게는 절대 풀 수가 없습니다.

조합(combinations)를 사용하든, 각 아이템을 넣거나 안 넣거나 하는 방법이든지간에 시간 복잡도가 최악이기 때문이죠.

간단히 생각해봤을 때 아이템을 넣냐 안넣냐라고 본다면 최대 100개의 아이템에 대해 계산해야 하니까..

2^100 이라는 연산 횟수가 나옵니다 😱

 

그래서 검색을 해보니까 굉장히 유명한 DP 알고리즘 중 하나더라구요.

코드만 슥 본다고 이해가 잘 되지 않으니 천천히 하나씩 이해해봅시다 🚀

 

item 리스트에 왜 [(0, 0)]을 넣어두고 시작하는가?

이건 사실 일종의 테크닉인데요, 들어있는 튜플이 의미가 있지는 않습니다.

다만 인덱스 에러를 피하기 위해서 미리 조치를 해둔 것이에요!

 

두 번째 for문을 보면 각각 row, col 이라는 변수의 범위가 1부터 시작한다는 것을 알 수 있습니다.

따라서 이와 모양새를 맞춰준 것 뿐입니다.

 

그럼 왜 인덱스를 1부터 시작해야 하는데..?

우선 bag 이라는 dp 테이블이 갖는 의미부터 생각해봐야 합니다.

문제에 제시된 예시를 표로 그려보면 다음과 같습니다.

그림이 조금 난잡하기는 한데.. 양해 부탁드립니다 🙏🏻

 

그래프의 행은 각 아이템의 (무게, 가치) 정보를 담고 있고, 열은 현재 가방의 무게 한도를 뜻합니다.

따라서 인덱스가 0인 행은 아이템에 대한 정보가 없고, 인덱스가 0인 열은 물건을 원래 담을 수 없기에 고려할 필요가 없습니다!

 

그럼 위 그림이 어떤 의미를 나타내는지 생각해보죠.

처음 숫자가 입력된 때는 (1,6) 지점의 13입니다.

왜냐하면 현재의 아이템 (무게:6, 가치:13)을 처음으로 넣을 수 있게 된 순간은 열: 무게한도 = 6 일 때이기 때문입니다!

 

그렇다면 현재의 아이템만 가지고 있을 때, 무게 한도가 7인 가방은 어떻게 될까요?

현재의 값이 그대로 옮겨질 것입니다.

다른 선택의 여지 없이 이전 (1, 6) 지점의 값을 가져올 수밖에 없기 때문이죠.

 

마찬가지의 과정이 각 행, 즉 각 아이템에 대해 수행됩니다.

 

중요한 건 초록색인데요, 초록색 맨 오른쪽을 보면 갑자기 14가 나타납니다.

이는 단순히 (2, 7) 지점의 값을 내려 받은 것이 아니라 (2, 4) 지점의 값과 현재 아이템의 가치 6((3, 3) 지점에 최초 기록됨) 을 합친 값입니다.

 

즉, 현재 아이템의 무게를 담을 수 있는 경우와 그렇지 않은 경우를 비교하여 더 큰 값을 취하게 된 것입니다.

이것이 위에 작성된 코드에서는 아래 부분에 해당합니다.

else: # 현재 아이템을 넣는 경우 or 현재 아이템을 담지 않는 경우 중 큰 값을 가져온다
    bag[row][col] = max(bag[row-1][col],bag[row-1][col-weight]+value)

 

한 눈에 바로 이해되는 논리가 아니라는 생각이 듭니다.

따라서 그림과 함께 천천히 각 행과 열이 의미하는 바가 무엇인지 잘 생각해 보시길 바랍니다!

(2차원 배열의 DP는 확실히 떠올리기가 쉽지 않네요 !)