[BOJ 12865/Kotlin] 평범한 배낭

코딩테스트

쵱니 2021. 2. 14. 21:28

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

분석

DP를 이용해서 주어진 무게 한게로 가장 높은 가치를 구하는 문제이다.

이 문제의 핵심은 DP의 핵심인 문제를 얼마나 단순화 할 수 있냐는 것이다.

먼저 무게를 기준으로 문제를 단순화 해보았다.

무게	1	2	3	4	5	6	7
가치	-	-	6	??

다이나믹 프로그래밍, 본인이 DP의 중요하다고 생각하는건 과거의 연산으로 현재의 값을 계산하는 것이다.

하지만 무게를 기준으로는 도저히 과거의 값으로 현재의 값을 유추할 수가 없었다.

그래서, 개수 기준을 한 개 더 추가해서 표를 다시 작성해보았다.

위와 같은 표가 나오고 결과로 14의 값이 출력된다.

예를 들어서 3행 7열의 빈 칸을 채워야할 차례이면 다음과 같이 계산해야 한다.

먼저 바로 전 행(물건 개수 2개( 6/13 과 4/8 ) 무게 7로 채울 수 있는 최대는 13이었다.

그리고 새로운 제품(3/6)을 추가해서 얻을 수 있는 값은

[ 바로 전 행(물건 2개 일 때)에서 무게가 4 일때의 가치] { 왜 무게가 4 ? => 구하고자 하는 무게 7 - 새로 추가된 제품 무게 3 }

새로운 제품의 가치

이다. ( => 8 + 6 = 14 )

그럼 3행 7열에 들어갈 값은 13과 14 중 큰 값이다.

그러므로 빈 칸에는 14의 값이 들어가야 한다.

이러한 방식으로 표를 다 완성시킨 후에 구하고자 하는 [물건 개수의 행]과 [총합무게의 열] 을 출력하면 된다.

최초 작성일 : 2021 - 02 - 14