BOJ #12865 평범한 배낭

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #12865 평범한 배낭

문제 풀이

0-1 냅색(0-1 Knapsack) 문제라고도 부르며 대표적인 DP문제로 소개되곤 한다. 다만 그 풀이는 하위 문제 분할이 잘 생각나지 않을 수 있으므로 한 번은 짚고 넘어 가야겠다.

가방에 들어가는 짐의 개수와 무게가 주어진 제약조건을 기준으로 1씩 분할된다고 해보자.

각 짐에 대해 탐색을 진행하되 0부터 W까지 탐색한다. 탐색에 쓰이는 짐의 무게가 탐색 중인 허용치보다 작거나 같을 때 이전 짐에서 탐색한 결과와 비교하여 갱신하면 되겠다.

시간제한이 빡빡한 편이여서 풀이 자체는 정답이지만 주소 할당이나 리스트 생성에서 비효율이 발생하면 여지없이 TLE를 출력한다.

python 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
cargo = []
for _ in range(N):
    cargo.append(list(map(int, input().split())))
dp = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(1, N + 1): # 각 짐에 대해
    for j in range(1, K + 1): # 각 저장용량에 대해
        if cargo[i - 1][0] <= j: # 만약 짐이 용량 이하라면
            dp[i][j] = max(
            dp[i - 1][j], # 이전 짐의 동일 허용치 값과
            dp[i - 1][c - cargo[i - 1][0]] + cargo[i - 1][1]
                # 이전 짐의 허용치-현재 짐 무게의 값 + 현재 짐 가치와 비교
            )
        else:
            dp[i][j] = dp[i - 1][j] # 용량보다 크면 이전과 값 동일
print(dp[N][K])

여기서 탐색 짐의 용량이 허용치보다 클 경우 굳이 탐색을 할 필요가 없다. 그리고 dp 배열도 굳이 2차원이 아니라 탐색 횟수는 별 차이 없겠지만 용량을 기준으로 1차원 배열로 만들 수 있을 듯 하다.

python 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
cargo = []
for _ in range(N):
    cargo.append(list(map(int, input().split())))
dp = [0 for _ in range(K + 1)] # 각 무게에 대해
for w, k in cargo:
    for c in range(K, w - 1, -1): # 마지막 용량부터 탐색 짐 무게까지
        dp[c] = max(dp[c], dp[c - w] + k) # 현재값, 용량-현재무게 + 가치
print(dp[K])