Algorithm/Acmicpc
1202 보석 도둑 [JAVA]
문제 분석https://www.acmicpc.net/problem/1202무게와 가격을 가진 N개의 보석이 있고최대 C의 무게까지 담을 수 있는 가방에 최대 1개의 보석을 담을 수 있으며 이런 가방이 K개가 있을 때 담을 수 있는 최대 가치를 구하는 문제다. 맨 처음에는 냅색같이 생겼다 싶었는데, 잘 읽어보니 K개에 최대 1개만 담을 수 있다고 적혀있었다. 다음으로 떠올렸던건 세그먼트 트리인데1. N개의 보석에 대해서 무게 순으로 쭉 정렬을 하고2. 각 무게의 시작 index를 저장하는 Map을 만들고3. 정렬된 배열을 기반으로 하는 최댓값 세그먼트 트리를 만들고4. 들어오는 가방마다그리디하게 0부터 해당 가방 크기에 해당하는 구간까지의 최댓값을 구하고5. 사용된 보석의 가치를 0으로 만들고 세그먼트 ..
