BOJ 18042 - Assimilation

set 활용법을 몰라서 개고생한 문제.. 너무 힘들었다.

---

체감 티어 : G1

태그 : greedy, set

 

모든 행성을 효율적으로 정복하려면 어떻게 해야 할까?

일단 다음과 같은 행동을 취해볼 수 있다.

 

1. 인구수가 가장 작은 행성부터 정복해 mobilization을 한다.

 

2. 인구수가 많은 행성부터 정복해 mobilization을 한다.

 

1번 아이디어는 반례가 생긴다는 것을 몇번의 관찰로 알아낼 수 있다.

그럼 이제 2번 아이디어를 가지고 어떤 식으로 가져가야 할지 생각해 보자.

 

먼저 고려해야 할 것은 어떤 행성들에서 충원 할 것이냐이다.

이는 최소한의 횟수로 충원 해야 하기에 가장 중요한 부분이다.

일단 전체 행성들의 합들을 이용해 충원 할 행성들을 정해볼 수 있다.

 

k 개의 우주선으로 정복할 수 있는 행성들 중 인구수가 가장 많은 행성을 정복한 후 바로 충원 한다.

이후 전체 행성들에서 정복한 행성을 제외하고 sum < k 가 될 때까지 정복 및 충원 해주면 된다.

 

만약 sum > k 이지만 더 이상 정복 및 충원을 할 수 있는 행성이 없으면 나머지 행성을 정복하지 못한다.

따라서 이 경우에는 -1을 출력해 주면 된다.

 

multiset을 이용해 구현을 하면 O(n log n)에 해결할 수 있다.