✓

태그:

CLASS 5 ESSENTIAL

보석? 일단 그리디! 이러면 안돼요 여러분

풀이 비스무리한거 보기

보석의 무게와 가치, 그리고 가방의 개수와 무게 한도가 주어졌을 때 최대로 휴대 가능한 가치를 출력하는 문제입니다. 일단 보석 문제는 전통적으로 그리디 알고리즘이 떠오릅니다. 그래서 보석은 보석의 가치, 가방은 무게에 따라 정렬합니다. 이제 가장 가치가 큰 보석부터 시작하여 이 보석을 담을 수 있는 가장 작은 가방을 골라 보석을 집어넣습니다. 가치 순서대로 모든 보석에 대해 이를 적용하면 얻을 수 있는 최대 가치를 구할 수 있습니다.

이미 사용한 가방인지는 분리 집합을 사용하여 구할 수 있습니다. 분리 집합의 루트를 이 가방의 한도보다 큰 가방 중 가장 작은 가방으로 설정하면 어떤 가방을 사용해야하는지 쉽게 구할 수 있습니다. 그리고 Path Compression 잊지 마세요!본인이 당함

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-14 23:40:09

---