12865 평범한 배낭 dp

골5

dp 문제였지만 완전탐색 느낌으로 조합적으로 풀려고 했다가 실패했다.

for 문으로 무게를 돌면서 재귀적으로 해당 무게에서 발생할 수 있는 모든 조합을 검색하려 했지만

당연하게도 시간초과!

dp로 풀어보려고 했는데, 뭔가 풀릴듯하면서 풀리지 않았다.

이유는 기존에 풀던 dp문제들은 그냥 리스트 끝까지 계속 최대값을 쌓아가면서 최대값만 구해내면 됬었는데, 이번 문제는 무게의 제한이 걸려있어서 중간에 무게의 합이 되면 쌓았던 최대값을 출력해내야 된다? 고 생각이 들었기 때문이다.

하지만 핵심은 이중 dp

배낭에 담을 수 있는 최대 무게 K와 인덱스 N을 둘이 함께 쌓아서 2차원 배열을 통해 최대값을 구해야 하는 문제였다.

알고리즘은:

1. 0 으로 채워진 [N+1][K+1] 의 배열을 만든다. 해당 배열은 최대값을 쌓아갈 2차원 배열이다.
   가로 K, 세로 N이 된다.

2. for 문을 돌면서 1~N, 1~K 를 모두 순회한다.
   시작이 1인 이유는 해당 값을 구할 때 이전 값(i-1)을 참조해야하기 때문에 index error를 방지하기 위해 1부터 시작한다. 0번째 배열에 들어있는 값은 모두 0으로 동일하다.

3. 만약 현재 찾고있는 N(짐) 의 무게가 현재 구하고 있는 무게(j: K의 for문 값)보다 작다면 내가 최대로 하고 있는 배낭의 짐무게가 짐무게보다 작다는 얘기이므로, 짐을 배낭에 넣을 수 없다는 이야기이다. 그러면 이전에 구했던 N(i-1 : 이전 짐일때 최대무게)의 최대값을 집어넣어야 한다.

4. 3번이 충족되지 않는다면 = 내가 현재 참조하는 짐(i)을 배낭에 넣을 수 있음.
   나는 현재 참조하고 있는 짐의 무게와 내 배낭의 최대 무게를 빼서, 그 나머지 값에 해당하는 최대 가치의 짐을 넣어야 함. 그렇게 되면 내가 현재 배낭의 최대무게에 최대로 가치를 높일 수 있는 값이 된다.

5. 이렇게 모두 for 문을 순회하고 나면 배열의 마지막 값이 최대값이 된다.

i, j 변수명이 난 풀이를 볼 때 헷갈렸어서 최대한 의미를 담을 수 있게 변수명을 짜보았다.

N, K = map(int, input().split(" "))

arr_weight = [0] * N
arr_value = [0] * N
max_value = 0
for i in range(N):
    arr_weight[i], arr_value[i] = map(int, input().split(" "))

ans = [[0 for _ in range(K+1)] for _ in range(N+1)]

def solution():

    for current_pack in range(1, N+1):
        for current_weight in range(1,K+1):
            # 해당 무게보다 j 값이 작으면 이전 값 가져옴 만약 크면
            if arr_weight[current_pack-1] > current_weight:
                ans[current_pack][current_weight] = ans[current_pack-1][current_weight]
            else:
                ans[current_pack][current_weight] = max(ans[current_pack-1][current_weight], arr_value[current_pack-1] + ans[current_pack-1][current_weight-arr_weight[current_pack-1]])

    print(ans[N][K])


solution()

dp를 1부터 계속 최대값을 쌓아간다는 개념을 명확하게 이해하고 있다면

조금 응용해서 풀어낼 수 있는 문제였다.