Greedy
-
[BOJ] 1202 보석 도둑PS/BOJ 2020. 7. 15. 14:51
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 알고리즘: Greedy 접근: 1. 가방에는 보석을 한 개만 넣을 수 있다. -> 각 가방은 본인이 담을 수 있는 보석 중에 가장 가치가 큰 보석을 가져야 한다. (Greedy 방식 접근) 다만, 무턱대고 가장 가치가 큰 보석을 집으면 안됨. ex) 3 2 1 100 11 20 3 1 20 5 무게가 20인 가방이 무턱대고 가장 가치가 높은 1짜리 보석을 넣으면 그 밑에 무게가 5인 가방이..