[Leetcode] 2439. Minimize Maximum of Array

문제 : https://leetcode.com/problems/minimize-maximum-of-array/description/

---

0부터 인덱싱된 n개의 음이 아닌 정수로 구성된 nums 배열이 제공됩니다.

한 번의 작업에서는 다음을 수행해야 합니다.

1. 1 <= i < n 인 정수 i를 선택합니다. nums[i] > 0 입니다.

2. nums[i]를 1 감소시킵니다.

3. nums[i-1]를 1 증가시킵니다.

 

작업 수행 후 nums의 최대 정수 값 중 가능한 최소 값을 반환합니다.

---

nums의 최대 정수 값 중 가능한 최소 값을 구하려면 모든 요소들을 평균 값으로 만들면 됩니다.

문제 2, 3번을 통해 알 수 있는 점은 뒤에 있는 nums 요소의 수는 앞으로 이동 가능할 수 있다. 입니다.

ex) [1, 2, 3, 4] -> [3, 2, 3, 2] (4의 2를 1로 이동시킴)

이를 반대로 생각하면 nums 요소의 앞에 있는 수는 뒤로는 이동이 불가능합니다.

따라서, 앞에서부터 탐색한 평균 값들보다 작은 값은 정답이 될 수 없습니다. 

nums = [3, 7, 1, 6]을 예로 든다면, 두 번째 요소까지의 평균 값은 [3, 7] -> [5, 5] 로 만들 수 있지만. 세 번째 요소까지의 평균 값을 [3, 7, 1] -> [4, 4, 3] 으로 만드는 건 불가능합니다. 

즉, 앞에서부터 탐색하면서 탐색한 요소들의 평균(소수점 반올림)값을 구하는데 이들 중 최대값을 구하면 정답이 됩니다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/2439.%20Minimize%20Maximum%20of%20Array.cpp