boj 2792 : LJUBOMORA

boj 2792 : LJUBOMORA

https://www.acmicpc.net/problem/2792

DP로 풀릴 수 있는가 보느라 한참을 고민했다.

하지만 의외로 간단하게 풀릴 수 있었음...

[1 ~ 가장 많은 보석 수]에서 이분 탐색으로 찾는다.

만약 보석을 적게 나눠준다면 모든 보석을 털 수 없다.

보석을 모두 털 수 있는 최소 갯수가 정답.

예제의

5 2

7

4

이 경우, 2개씩 나눠주면, 2 2 2 1 2 2로 6명이 있어야 하므로 모든 보석을 털 수 없다.

3개씩 나눠주면 3 3 1 3 1로 5명에게 털 수 있다.

따라서 5명에게 나눠주면 모든 보석을 털 수 있는 최소 보석수는 3개이다.

이 방법으로 해결하면 시간복잡도는 MlogM