[백준] #12865 평범한 배낭(python)

수영·2022년 8월 20일

DP Python3 백준

백준

목록 보기

39/117

📌문제

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

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

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

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

출력

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

예제 입력

예제 출력

백준 12865번 문제

💡Idea

사실 문제를 보고 DP를 통해서 풀 수 있을 것이라고 생각했었지만, 바로 접근을 하기가 쉽지 않았습니다.

하지만 조금 생각해보면 다른 여느 DP 문제들과 크게 다르지 않습니다.

1 ~ N의 범위 내에서 물건을 한 개씩 추가합니다.

1 ~ K의 범위 내에서 버틸 수 있는 최대 무게를 하나씩 늘려갑니다.

주어진 물건의 개수와 버틸 수 있는 최대 무게 내에서 가질 수 있는 최대 가치를 찾습니다.

최종적으로 N개의 물건과 K의 버틸 수 있는 무게에서 가질 수 있는 최대 가치를 구할 수 있습니다.

예를 들어봅시다!

위의 예시와 같은 상황에서, 1번 물품이 가질 수 있는 최대 가치를 1 ~ K의 버틸 수 있는 무게 범위에서 찾아보면 아래와 같습니다.

🎒 1번 물품(무게 : 6 / 가치 : 13)

1번 물건만 존재하는 경우,

버틸 수 있는 최대 무게가 1 ~ 5일 때 가질 수 있는 최대 가치는 0
버틸 수 있는 최대 무게가 6 ~ 7일 때 가질 수 있는 최대 가치는 13
-> 1번 물건을 배낭에 넣을 수 있기 때문

🎒 2번 물건 추가(무게 : 4 / 가치 : 8)

2번 물건이 추가되어 1번, 2번 물건이 있는 경우,

버틸 수 있는 최대 무게가 1 ~ 3일 때 가질 수 있는 최대 가치는 0
버틸 수 있는 최대 무게가 4 ~ 5일 때 가질 수 있는 최대 가치는 8
-> 2번 물건을 배낭에 넣을 수 있기 때문
버틸 수 있는 최대 무게가 6 ~ 7일 때 가질 수 있는 최대 가치는 13
-> 버틸 수 있는 무게가 6 ~ 7인 경우에 1번 물건만 존재할 때의 최대 가치와 비교하여 2번 물건을 넣을지 말지 결정할 수 있습니다.
-> 1번 물건 혹은 2번 물건 중 하나만 넣을 수 있는데, 1번을 넣는 것이 더 큰 가치를 가집니다.

위와 같이 n번째 물건을 추가할 때마다, 각 버틸 수 있는 최대 무게마다 n-1번째 물건을 가졌을 때의 최대 가치와 n번째 물건을 포함했을 때의 최대 가치를 비교합니다.

따라서 아래와 같은 점화식을 세울 수 있습니다.

$n$ 을 물건의 개수, $k$ 를 버틸 수 있는 최대 무게, $w$ 를 $n$ 번째 물건의 무게, $v$ 를 $n$ 번째 물건의 가치라고 할 때,
$P_{nk} = max(P_{n-1, k}\;,\;\; P_{n-w} + v)$

💻코드1

⏰ 시간 : 7076 ms / 메모리 : 281028 KB

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
arr = [[0, 0]] # 1 base
dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)] 
for _ in range(N): # arr에 물건 [무게, 가치] 추가
    arr.append(list(map(int, input().split())))

for n in range(1, N + 1):
    for k in range(1, K + 1): 
    w, v = arr[i][0], arr[i][1] # n번째 물건의 무게와 가치
        if k < w: #1
            dp[n][k] = dp[n - 1][k]
        else: #2
            dp[n][k] = max(v + dp[n - 1][k - w], dp[n - 1][k])

print(dp[N][K])

📝코드 설명1

변수

arr : 물건의 무게와 가치를 담은 리스트로, arr[n]번에는 n번째 물건의 무게와 가치가 저장되어 있습니다.
dp : dp[n][k]에는 n번째 물건까지 있을 때 버틸 수 있는 최대 무게 k에서 가질 수 있는 최대 가치가 저장되어 있습니다.

#1 : 버틸 수 있는 무게인 k보다 n번째 물건이 무거우면 배낭에 n번째 물건을 넣을 수 없습니다. 따라서, n번째 물건을 넣지 않았을 때의 최대 가치를 dp[n][k]에 넣어줍니다.
즉, n-1번째 물건까지 있고, 버틸 수 있는 무게가 k일 때의 최대 가치인 dp[n-1][k]를 넣어줍니다.

#2: 만약 버틸 수 있는 무게인 k보다n번째 물건의 무게가 더 작다면, n번째 물건을 배낭에 넣었을 때의 최대 가치와 넣지 않았을 때의 최대 가치 중 더 큰 값을 넣어주도록 합니다.

💻코드2

⏰ 시간 : 3772 ms / 메모리 : 33668 KB

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
arr = [[0, 0]]
dp = [0 for _ in range(K + 1)]
for _ in range(N): 
    arr.append(list(map(int, input().split()))) # arr에 물건 [무게, 가치] 추가

for n in range(1, N + 1):
    w, v = arr[n][0], arr[n][1] # n번째 물건의 무게와 가치
    for k in range(K, w - 1, -1): #1
        dp[k] = max(dp[k], dp[k - w] + v)
print(dp[K])

📝코드 설명2

코드 1처럼 2차원 배열을 통해서 문제를 해결할 수도 있지만, 1차원 배열만으로도 문제를 해결할 수 있습니다.

코드 1처럼 n번째 물건까지 있고 버틸 수 있는 무게가 k일 때의 최대 가치를 전부 저장해두지 않습니다.
대신, 버틸 수 있는 무게가 k일 때의 최대 가치를 저장합니다.
이 때 동일하게 1~N번 까지의 물품이 있을 때의 최대 가치를 확인하면서 값을 갱신해줍니다.