2학년 때 C++를 이용해 배웠던 DP인데 과제로 제출했던 코드를 찾으려고 하니 찾을 수 없어 새로 작성했습니다.
백준의 12865번 문제입니다.
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
간단히 정리하면
첫 줄에 물건의 수 n과 허용무게 k가 주어지고
다음 줄부터 각 물건의 무게w와 v가 주어지는데
허용가능한 물건n개와 무게k에서 최대 가치를 구하는 것입니다.
코드
라인해석
코드는 선언/첫반복문/두번째반복문 3개 구간으로 나누겠습니다.
weights = [0]
values = [0]
number_n, max_k = map(int,input().split())
dp = []
dp.append([0]*(max_k+1))선언 부분입니다.
weights와 values는 각 물건의 무게와 가치를 순서대로 입력합니다.
class혹은 dictionary를 사용하려 했으나 class를 선언하기엔 문제가 간단하고 dictionary를 선언하는 경우 전 값에 접근성이 떨어져 배열로 사용하였습니다.
number_n과 max_k는 첫 줄에 입력받는 물건의 수와 무게입니다.
dp는 2차원 배열로 물건수x최대무게의 배열입니다.(풀이방식 특성상 0번째 행과 열을 하나씩 추가했습니다.)
for _ in range(number_n):
sec_string = input().split()
weights.append(int(sec_string[0]))
values.append(int(sec_string[1]))
dp.append([0]*(max_k+1))
반복문을 통해 물건의 무게와 가치를 배열weights와 values에 추가해줍니다.
동시에 dp배열도 각 값을 0으로 초기화 시켜줍니다.
for i in range(1,number_n+1):
for j in range(1, max_k+1):
if weights[i] <= j:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i])
else:
dp[i][j] = dp[i-1][j]이중 반복문을 통해 dp배열의 값을 넣어줍니다 반복 횟수는 물건종류x최대무게입니다.
첫 if문에서 현재j값이 i번째 물건의 무게보다 작거나 같은 경우 dp의 값을 변경시키는데
이전 물건의 배열에 현재 물건을 넣지 않은 가치(dp[i-1][j])와
이전 물건의 배열에서 현재 물건을 추가했을 경우(dp[i-1]j-weights[i]]+values[i])를 비교해서 더 높은 가치를 가지는 경우의 값으로 dp의 값을 정해줍니다.
(여기서 첫번째 물건도 이전 물건과 비교해야하기 때문에 행을 하나 추가했습니다.)
else의 경우 현재 물건의 배열에서 이전 값을 그대로 옮겨줍니다.
위 반복문을 통해 dp의 값이 정해졌을 때 마지막값, 즉 모든 물건이 배열에 들어가는 기회가 있으며 최대 무게의 조건에서 가장 높은 가치를 가지는 경우의 값이 답이 됩니다.
