[BOJ] 12865번: 평범한 배낭

https://www.acmicpc.net/

 

문제풀이

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

12865번: 평범한 배낭

가장 일반적인 냅색 문제이다. dp를 통해 해결할 수 있는데 생각보다 조건을 생각할 것이 많았다. 나의 경우 다이나믹프로그래밍 배열을 1차원으로 작성하는 것을 선호하는데 이 경우에는 2차원 배열로 먼저 작성했다. 

 

2차원 배열의 행은 각 물건을 나타내며, 열은 무게를 나타낸다. 0번째 행, 0번째 열은 비워두기 때문에 (n+1)*(k+1)크기의 배열을 만들었다.  각 행열은 해당 물건을 포함했을 때 해당 열의 무게 안에서 최대 가치이다. 이를 기반으로 코드를 작성했다. 하지만 이경우 추가적인 조건을 생각해줘야해서 1차원 배열로 구현했다.

 

Python3

2차원 배열 code

import sys
n, k = map(int, sys.stdin.readline().split())
weight = [0]*(n+1)
values = [0]*(n+1)
for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    weight[i+1] = w
    values[i+1] = v
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, k+1):
        if weight[i] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + values[i])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][k])

2차원 배열로 구현 시에는 주어진 무게(열)에 대해 특정 물건(행)의 무게를 비교한다. 이 물건의 가치와 이 물건을 담았을 때 남은 무게에 대한 최대 가치를 더한 값과 이 물건을 안담았을 때 이 무게에서의 최대 가치를 비교하여 큰 값으로 현재 물건의 주어진 무게에 대한 최대 가치를 구한다.

하지만 이경우 특정 물건의 무게가 주어진 무게보다 작거나 같을 때만 가능하다. 따라서 이 외의 경우에 대해 따로 처리가 필요하다. 

나는 이 경우에 대해 따로 처리하는 코드를 작성하는게 싫어서 1차원 배열을 사용했다.

 

1차원 배열 code 

import sys
n, k = map(int, sys.stdin.readline().split())
weight = [0]*(n+1)
values = [0]*(n+1)
for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    weight[i+1] = w
    values[i+1] = v
dp = [0]*(k+1)
for i in range(1, n+1):
    for j in range(k, 0, -1):
        if weight[i] <= j:
            dp[j] = max(dp[j], dp[j-weight[i]] + values[i])
print(dp[k])

1차원 배열의 경우 값이 계속 누적되기 때문에 따로 특정 물건의 무게가 주어진 무게보다 클 때에 대한 예외처리가 필요없다. 하지만 이경우에서의 문제는 2차원 배열에서 처럼 무게를 0일때부터 살펴보게 되면 우리가 필요했던 변경되기 전값이 사라지게 된다. 따라서 무게가 최대일 때부터 0일때로 순서를 바꿔서 살펴보는게 필요하다.

 

여기서 또 궁금했던 점은 주어진 무게가 6일때 물건의 무게가 3이라면, 또 물건의 가치가 이전 6무게에 대한 최대 가치보다 크다면 무게가 3인 물건을 2개 사용할 수도 있지 않을까?에 대한 것이었다. 하지만 이경우에 대해서는 생각할 필요요가 없다. 위에서 최대무게에서 0무게로 접근하도록 순서를 바꾸면서 저절로 해당 경우에 대한 처리가 이루어졌기 때문이다.

 

2차원 배열보다 조건을 안쓰고 배열도 줄일 수 있어서 훨씬 좋은 코드가 되었다.