[Kickstart][2020][Round A] 3. Workout

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f5b

---

Tambourine 씨는 N개의 휘트니스 프로그램 세션을 준비했다. i번째 세션은 M[i] 분 동안 진행될 것이다.

진행 시간은 반드시 증가한다. (M[i] < M[j], i < j)

휘트니스 프로그램의 난이도는 연속되는 세션의 진행시간 차이들 중 최대값이다.

그녀는 난이도를 낮추기 위해 최대 K개의 추가 세션을 추가하고자 한다. 이 때, 추가 세션들도 진행 시간은 반드시 증가해야한다.

기존 세션들에서 최대 K개의 세션을 추가한다고 할 때, 가능한 난이도의 최소값은 어떻게 되는가?

---

이분탐색 문제이다.

구하고자 하는 값이 난이도의 최소값이므로 역으로 난이도를 지정해두고 해당 난이도를 구하기 위해 세션을 추가할 때, K개 이하로 가능한지 불가능한지로 가능한 난이도 범위를 좁혀나간다.

처음 가능 범위는 1~10^9이다. 10^9인 이유는 M 배열 요소들중 최대값이 최대 난이도가 될 수 있기 때문이다. (정확히 말하면 최대값 - 1). 최대 난이도를 구하기 위해 M 배열을 한 번 탐색해도 되지만 조건에서 M[i]의 가능 범위가 최대 10^9라고 했기 때문에 이를 이용해서 최대값을 세팅했다.

이진 탐색을 위해 가능 범위의 중간 값을 난이도로 가정한다. 즉, 난이도 = (1 + 10^9) / 2.

난이도가 가능한지 판단하기 위해서 추가되는 세션을 구해야 한다.

따라서 M 배열을 탐색하면서 연속되는 세션의 시간 차이 / 난이도 의 합을 구한다.

cf. 연속되는 세션의 시간 차이 = M[i] - M[i-1] - 1

 

구한 합이 K개 이하라면 현재 난이도는 정답이 될 수 있다. 따라서 가능 범위를 1~10^9 에서 1~난이도 로 변경한다. 최대값을 갱신하는 이유는 가능 난이도 중 최소값이 정답이기 때문이다.
구한 합이 K개보다 크다면(초과) 현재 난이도는 정답이 될 수 없다. 따라서 가능 범위를 1~10^9 에서 난이도~10^9 로 변경한다. 최소값을 갱신하는 이유는 현재 난이도가 정답이 될 수 없기 때문에 현재 난이도보다 작은 값들은 절대 정답이 될 수 없기 때문이다. (ex. 범위가 1~10, K= 1일 때. 현재 난이도가 3이라 가정했을 때, 조건상 구할 수 있는 난이도의 최소값은 4(1~5, 6~10) 이므로 정답이 될 수 없고. 3보다 작은 1, 2도 정답이 될 수 없다.)

 

범위의 최대 값 - 최소 값이 1보다 큰 경우 위 과정을 반복한다. (1을 경계로 잡은 이유는 가능한 난이도의 최소값이 1이기 때문)

시간 복잡도는 O(N logM).

N은 배열 M의 크기이고 M은 M배열 요소값들 중 최대값이다. 여기서는 M[i] 가능 범위인 10^9을 초기 난이도의 최대값으로 세팅했기 때문에 M = 10^9 가 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundA/3.%20Workout.cpp

---

내 머리는 아직 완탐밖에 모르는거 같다. 이진탐색 알고리즘을 알아도 아직 "이 문제는 이진탐색으로 풀면 나오겠다!" 라는 사고로 가지는 않는 듯. 이진탐색 문제를 백준에서 찾아서 좀 풀어봐야겠다.