귤나무

현재 귤나무에 남은 귤의 수를 $M$이라고 하겠습니다.

$M$이 $A$의 최솟값보다 작아지기 전까지는 적어도 한 마리의 곰곰이가 귤을 딸 수 있습니다.

따라서 문제를 다음과 같이 표현할 수 있습니다.

• $a := 0$ 으로 두고, $A$를 순회하며 $a + A_i <= M$ 인 경우 $A_i$를 $a$에 더합니다.
• $M$을 $a$만큼 감소시킵니다.
• 이를 $M < min(A)$이 될 때까지 반복합니다.

첫 과정에서 순회를 마친 후 $a$가 결정된 상황을 생각해봅시다.

이제 $M$에서 $a$를 빼고 다시 $a$를 구해야 하는데, 사실 $M$이 $a$보다 작아지기 전까지는 $a$의 값이 변하지 않습니다.

$M$이 $a$ 이상이라면 기존에 더해진 $A_i$는 항상 더해지고, $M$은 계속 감소하기 때문에 새로운 $A_i$가 더해질 일이 없기 때문입니다.

따라서 $M$을 $a$만큼 감소시키는 대신, $M$에 $M \space mod \space a$를 할당해도 됩니다.

$M$ 이하의 수 $a$로 $M$을 나눈 값의 나머지는 항상 $floor(M / 2)$ 이하이기 때문에, 위 시행은 최대 $log M$번만 이루어집니다.

따라서 전체 시간복잡도 $cal(O)(N log M)$ 에 문제를 풀 수 있습니다.