728x90
분석
DP를 이용해서 주어진 무게 한게로 가장 높은 가치를 구하는 문제이다.
이 문제의 핵심은 DP의 핵심인 문제를 얼마나 단순화 할 수 있냐는 것이다.
먼저 무게를 기준으로 문제를 단순화 해보았다.
무게 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
가치 | - | - | 6 | ?? |
다이나믹 프로그래밍, 본인이 DP의 중요하다고 생각하는건 과거의 연산으로 현재의 값을 계산하는 것이다.
하지만 무게를 기준으로는 도저히 과거의 값으로 현재의 값을 유추할 수가 없었다.
그래서, 개수 기준을 한 개 더 추가해서 표를 다시 작성해보았다.
제품번호 | 무게 | |||||||||
무게 | 가치 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
6 | 13 | 제 품 개 수 |
1 | - | - | - | - | - | 13 | 13 |
4 | 8 | 2 | - | - | - | 8 | 8 | 13 | 13 | |
3 | 6 | 3 | - | - | 6 | 8 | 8 | 13 | 14 | |
5 | 12 | 4 | - | - | 6 | 8 | 12 | 13 | 14 |
위와 같은 표가 나오고 결과로 14의 값이 출력된다.
해석
제품번호 | 무게 | |||||||||
무게 | 가치 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
6 | 13 | 제 품 개 수 |
1 | - | - | - | - | - | 13 | 13 |
4 | 8 | 2 | - | - | - | 8 | 8 | 13 | 13 | |
3 | 6 | 3 | - | - | 6 | 8 | 8 | 13 | 빈 칸 | |
5 | 12 | 4 |
예를 들어서 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
728x90
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ 1655 / 파이썬] 가운데를 말해요 (0) | 2021.08.26 |
---|---|
[BOJ / 10217] KCM Travel 파이썬 (0) | 2021.08.20 |
[BOJ 1316/Kotlin] 그룹단어 체커 (0) | 2020.10.08 |
[BOJ/5622번] 전화 다이얼 (0) | 2020.10.04 |
[BOJ/1065번] 한수 (0) | 2020.10.04 |