[백준 12865] 평범한 배낭

[BanApp]

import sys

n,k = map(int,sys.stdin.readline().split())

arr = []
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
arr.sort(key=lambda x: (x[0]))

tmp = [[0]*(k+1) for _ in range(n+1)]

for i in range(n+1):
    for j in range(k+1):
        if i == 0 or j == 0:
            tmp[i][j] = 0
        elif arr[i-1][0] <= j:
            tmp[i][j] = max(arr[i-1][1] + tmp[i-1][j-arr[i-1][0]],tmp[i-1][j])
        else:
            tmp[i][j] = tmp[i-1][j]

print(tmp[-1][-1])

전에 풀었다가 실패했던 문제다.
냅색 알고리즘을 모르고 무작정 시도했어서 계속 실패를 맛봤던 문제다.
우선 주어진 물건의 개수와 무개제한 보다 하나씩 크게 해서 이차원 리스트를 만든다.
이러한 이차원 리스트 tmp의 행은 가방에 넣을 수 있는 물건의 개수 열은 가방에 담을 수 있는 최대 무개를 제한한다.
예를 들어 tmp[2][5] 의 2개의 물건을 골라서 무게의 합이 5가 되는것의 최대값을 넣는것이다.
이게 성립하기 위해서는 무게를 기준으로 오름차순 정렬을 해줘야 한다.
여기서 tmp[I][j] 는 바로 위에 존재하는 것(tmp[i-1][j]) 과 해당 물건의 무개와 제한 무개를 뺀 tmp의 인덱스에 접근해서 더 큰것을 넣어준다.
이를 반복하면 tmp의 마지막 원소는 우리가 찾는 가치합의 최대가 된다.

민준이가 좋아하는 DP게임.. 게임 스타트.. 숙취는 힘들어..

[ghdcksgml1]

ㅋㅋㅋㅋ 오 냅색 처음 보면 이해어려운 알고리즘...