다이나믹 프로그래밍 - 0/1 Knapsack 문제
https://www.acmicpc.net/problem/12865
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)으로 해결해야하는 문제였다. 실버 정도의 디비 문제는 몇개 풀어봤는데 이문제는 도저히 풀이방법이 떠오르지 않아서 검색을 해보았다.
찾아보니 0/1 Knapsack 이라는 유형의 문제이고 dp를 통해 해결하는 문제라는데 아직 dp 문제를 한두문제 풀어본 나에게 아이디어를 떠올리긴 너무 힘들었다. 사실 문제의 설명을 보고도 이해하는데 한참 걸렸다. dp문제는 아이디어 떠올리는게 너무 어려워서 다양한 유형의 문제를 무식하게 많이 만나보고 해결방법을 외워두는 방법 밖에는 없는 것 같다.
풀이는 아래와 같다.
참고
[백준 12865] 평범한 배낭
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무..
gumeum.tistory.com
마치면서
일주일 가량 TIL을 쓰지 못했다. 코테를 준비하느라 그랬다지만 역시 글을 쓰지 않으니까 역시 공부의 밀도는 더 약해지는 것 같았다. 오늘도 많은 공부를 하진 못했지만 정말 조금 공부한 것이라도 부끄러워하지 말고 꾸준히 써내려가면서 공부량을 늘려나가야겠다.
'TIL' 카테고리의 다른 글
| TDD의 장점 (0) | 2022.04.08 |
|---|---|
| [TIL 2022-3-7] JPQL, BOJ10830 행렬 제곱 (0) | 2022.03.08 |
| [TIL 2022-2-28]스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (0) | 2022.02.28 |
| [TIL 2022-2-25] JPA 값 타입, PriorityQueue (0) | 2022.02.26 |
| [TIL 2022-2-25] JPA, DFS (0) | 2022.02.25 |
