[백준 12865번] 평범한 배낭

원본 링크

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

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력

4 7
6 13
4 8
3 6
5 12

예제 출력

14

주 알고리즘 분류

• DP(다이나믹 프로그래밍)

나만의 풀이

사실 맨 처음에 이 문제를 봤을 땐 무조건 BackTracking이다 생각했다.
학부에서 관련 수업을 들었을 때 해결할 수 있는 방식을 백트래킹으로 배웠기 때문이다.
하지만 알다시피 백트래킹의 최악 시간 복잡도는 상당수준을 웃돈다.
np문제를 조금 더 효율적으로 풀기 위해 BackTracking을 쓰는 것이 아니겠나.

따라서 2초내엔 위 방식으로 풀 수 없다 느꼈고, 추가적인 탐색을 했다.
알고보니까 무려 DP(다이나믹 프로그래밍)문제라고 한다.
다른 선구자(?)들의 자취를 밟아가며 풀이 과정을 봤는데 그냥 감탄사밖에 안 나온다.
어떻게 저런 생각을 했을지...
아무튼 이번 문제는 내 것으로 이해시킨다는 과정으로 하나씩 풀이 과정을 기술하려 한다.

먼저, 입력 속도를 줄이기 위해서 기존에 쓰던 input()대신 다른 메소드를 이용했다.

# Input 속도 줄이기 용
import sys
input = sys.stdin.readline

위 형태로 input 함수를 바꿔주고, 이후 별도로 input()에다가 .rstrip()을 붙여줘서 혹시 모를 개행문자도 제거할 생각이다.
문자열을 다루는 문제는 아니지만 익숙해지기 위해서 input().rstrip()의 형태로 사용하려 한다.

데이터를 입력 받는 부분은 기존의 형태와 비슷하므로 선언된 변수명만 기술하고 넘어가려 한다.
적절하게, N, K, weight, value라는 친구로 값을 할당했다.
이제, 본격적인 문제 분석을 시작하자.

먼저 위 그림과 같은 DP라는 이차원 배열(리스트)을 생성하였다.
여기에다가 선택한 물건들에 따른 Value 정보를 저장할 생각이다.
행은 i번째 물건을 나타내며, 열은 Max 무게의 값을 나타낸다.
주어진 예제에선 가방의 무게가 7이라 가정했으므로, Max무게는 7까지 고려하게 된다.

위와 같이 Redundant한 항목들은 0으로 채워넣으면 된다.
Max무게가 0인 경우는 당연히 어떤 물건이든 들어갈 수 없으므로 값어치가 0이 될 것이다.
그리고, i=0인 경우는 향후 알고리즘 구현의 편의를 위해 추가한 행이라 보면 된다.
즉, 저 자체로는 특별한 의미가 없다. (굳이 말하자면 물건을 아직 안 고른 상태 정도.)

이제 값을 채워넣을건데, 각 행마다 우측으로 하나씩 넣어갈 예정이다.
참고로 여기서 i번째 행에 도달했다는 의미는, i번째 물건까지 최적값을 비교했다는 의미라 보면 된다.

우선 무게가 6이고 가치가 13인 물건하에 Max 무게별로 경우를 생각하자.
일단, 가방의 최대 무게가 6보다 작으면 물건을 담을 수 없다.
반면 위의 주황색 위치와 같이 무게가 6이상이 되면 물건을 담을 수 있다.
따라서 그 이후는 13이라는 가치를 지니게 된다.

이번엔 두 번째 무게 4, 가치 8 물건을 담는다 생각하자.
역시, Max 무게가 4 이상이면 해당 물건을 담을 수 있으므로 8이라는 값을 지니게 된다.
그리고, Max 무게가 6 이상인 경우에는, 아까 1번째 물건을 담는 게 더 효과적이므로 13의 값을 지닌다.
따라서 이 경우는 13이 채워진다.

문제는 위 경우에서 시작된다.
앞서 3번째 물건 무게 3, 가치 6을 기준으로, Max 무게가 3인 경우, 4인 경우, 6인 경우는 값이 달라지지만 위 규칙에 따라서 값을 채워넣을 수 있게 된다.
그러나 Max 무게가 7인 경우가 변수가 되겠다.

3행 7열의 원소의 최적값을 알아내기 위해선 두 가지 값을 비교해야 한다.
하나는, 그 이전까지 누적해서 비교했던 가치(DP[2][7])이며, 나머지 하나는 현재 물건(value[3])을 선택한 다음 남은 공간에 기존의 최적값을 넣었을 때(DP[3][7-3])의 합산 가치가 되겠다.
위 그림에 나와있는 식을 보면 다소 알록달록하긴 하나, 저렇게 점화식을 구성할 수 있다.

최종적으로 나머지 행도 채워준다.
Max value가 5인 경우에 추가로 12가 들어간다는 것을 빼면 큰 변화는 없다.
결론적으로 우리가 구하는 값은 DP[4][7]에 해당하는 값이 되며, 14라는 출력을 얻게 된다.

앞선 과정을 정리하면 다음의 case로 일반화가 가능할 것이다.

if weight[i-1] > maxW:  # weight_i > maxW인 경우
    DP[i][maxW] = DP[i-1][maxW]
else:  # 비교해야 하는 파트.
    DP[i][maxW] = max(DP[i-1][maxW-weight[i-1]]+value[i-1], DP[i-1][maxW])

i는 1에서 N까지의 값을 지니며, maxW는 1에서 K까지의 값을 지닌다.
만일 현재 max 무게보다 선택한 물건의 무게가 크다면 (# weight_i > maxW인 경우) 그 이전 단계의 값을 그대로 채워넣는다.
앞선 도식으로 설명하자면, 현재 칸의 위의 값을 가져온다 생각하면 된다.
그 반대의 case는 앞선 점화식을 이용해서 값을 얻어내면 된다.
주의점은 위 코드에선 i가 0이 아닌 1에서 출발했기 때문에 weight와 value를 참고할 경우 i-1이라는 인덱스로 접근해야 한다.

아, 그런데 여기에서 1행 6열과 같이 맨 처음에 13이라는 값은 어떻게 채워지나 하는 의문이 들 것이다.
위 값을 채우는 과정도 점화식을 이용하는 분기에서 채워지게 된다.
상세하게 설명하진 않겠고, 그냥 아래의 식을 토대로 이해하면 될 것 같다.
DP[1][6] = max(0+13, 0)

정리한 전체 코드이다.

# Input 속도 줄이기 용
import sys
input = sys.stdin.readline

# 데이터 입력
N, K = map(int, input().rstrip().split())
weight, value = [], []  # 각각 무게와 가치
for _ in range(N):
    W, V = map(int, input().rstrip().split())
    weight.append(W)
    value.append(V)

DP = [[0]*(K+1) for _ in range(N+1)]  # 초기화

for i in range(1, N+1):
    for maxW in range(1, K+1):
        if weight[i-1] > maxW:  # weight_i > maxW인 경우
            DP[i][maxW] = DP[i-1][maxW]
        else:  # 비교해야 하는 파트.
            DP[i][maxW] = max(DP[i-1][maxW-weight[i-1]]+value[i-1], DP[i-1][maxW])

print(DP[N][K])

사이트에선 난이도가 낮은 문제라고 등록되어 있다.
그런데 내 생각엔 DP만큼 까다로운 문제가 있을까라는 생각이 든다.
물론 다른 문제들도 특정 알고리즘을 모르면 못 푼다는 특징은 있다.
그러나 DP문제는 직접 case by case로 쪼개서 일반화를 수행하지 못하는 이상 구현하기가 힘들다고 본다.
이른바 단순 암기로는 풀 수 없고 직관이 필요한 문제라 생각든다.
별 수 없지만 이런 유형의 문제들을 계속 풀어보는게 해결책이라 생각한다.

이와는 별개로 문제 상황을 읽어보면 눈물난다. (입대..)