[DP] 백준 12865. 평범한 배낭

문제 풀이 프로세스 (오답)

1. 문제의 주요 변수들 명시

2. DP의 빈배열이 있다고 가정하고, 문제의 조건에 맞는 답을 나열해보기

3. 나열한 것들 중에서 규칙찾기

# n 개의 물건, 최대 100개
# k 가용 무게
# w 무게와 v 가치

 

    y = 무게
d[x][y] = 가치 총합?
d[x][0] = 0
d[x][1] = 0
d[x][2] = 0
d[x][3] = 6
d[x][4] = 8 => max(d[x][3], d[x][4])
d[x][5] = 12 => max(d[x][4], d[x][5])
d[x][6] = 13 => max(d[x][5], d[x][6])
d[x][7] = 14 => max(d[x][6], d[x][3]+d[x][4]) # 이중 포문으로 탐색할 부분


d[무게] = 가치
무게랑 물건개수

오답으로 빠진 이유

나열해보니, 이차원일 필요가 없다고 느꼈고, 따라서 변수 things를 제거했다. (비극의 시작)

바텀업으로 d[i] = max(d[i], d[i-j]+d[j]) 만 하면 답이 나온다고 생각했다. 그러나 물건은 하나씩이기 때문에, 이미 하나 들어가 있으면, 하나 또 넣을 수가 없다는 점을 간과했다. 예를 들어 i = 2이고, j = 1일 때, 무게 1이자 가치가 7인 물건을 이미 담았다고 치자. 그렇다면 d[1] = 7 로 이미 들어가 있는데, d[2]를 구하면서 d[2] = max(d[2], d[1]+d[1]) 을 하게 되면 무게 1인 물건을 두번 담는 게 제일 가치가 높게 나올 수 있다는 것이다. 또, 물건을 빼면 그 물건에 해당하는 무게와 가치를 동시에 빼줘야 한다..!

결국 물건 인덱스가 필요하기 때문에 d 빈배열은 2차원이어야하고, 물건 리스트(things)를 별도로 만들어서 빈배열에 제때 물건의 정보를 할당해줄 필요가 있다.

 

위 부분을 수정하게 되면, 결정적으로 for문의 비교 구문이 생긴다. 새로 넣을 물건의 무게(w)와 현재 가용 무게(j)의 필요성을 놓친 게 큰 실수였다. 물건을 순차적으로 확인하게 되면서, 무게를 1단위가 아니라 물건 마다의 고유 무게 단위별로 탐색하게 된다. 새로 넣을 무게가 가용 무게보다 작을 경우 이전의 값을 그대로 전수받게 된다. d[i][j] = d[i-1][j]

반대로 새로 넣을 물건의 무게가 클 경우, 이전 물건을 j무게까지 넣은 값과 현재 물건을 넣게 될 가치 중 큰 값을 선택하게 된다.

이전 물건에 대한 것은 d[i-1][j]에 해당하고, 

이번 물건을 새로 넣게 되는 값은, 이번 물건에 해당하는 무게를 제거한 가치 d[i-1][j-w] 에 새로 넣을 가치 (v)를 더해줌으로써 구할 수 있다. d[i-1][j-w]+v

d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

 

오답 코드

d = [0]*(k+1)
for _ in range(n):
    w,v = map(int, input().split())
    if d[w] != 0:
        d[w] = max(d[w], v)
    else:
        d[w] = v

 

적절한 코드

import sys
sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline
n,k = map(int, input().split())

# n 개의 물건, 최대 100개
# k 가용 무게
# w 무게와 v 가치

d = [[0]*(k+1) for _ in range(101)]
things = [[0,0]]
for num in range(n):
    w, v = map(int, input().split())
    things.append([w, v])

for i in range(1,n+1):
    for j in range(1, k+1):
        w = things[i][0]
        v = things[i][1]
        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)


print(d[n][k])

 

교훈

* 문제의 특성상 고유 물건을 넣었다 뺐을 때 생기는 제약 조건 유의하기

* 처음에 쓰던 방식들이 맞았었는데, 그대로 쭉 해볼걸, 아쉽다

* 무게 비교하고 가치를 할당해야 한다는 게 (for 내부의 비교문) 어색했다

* 이 문제는 대표 유형이니까 반복해서 풀면 외워질 듯..!

 

참고

https://hongcoding.tistory.com/50