최대 C번 잘라내어 maxL을 초과하는 조각이 생기지 않도록 하는 것이 가능한지를 bool로 반환하는 func를 정의하고 파라메트릭 서치를 합니다.

bool func(int maxL);

처음 자르는 위치도 찾아야 해서 오른쪽부터 스캔하면서 이전에 자른 위치와 현재 위치의 차가 maxL을 초과할 때, 바로 전의 루프에서 확인한 위치를 자른 위치로 갱신합니다. 또한 루핑 중에 인접한 위치 사이의 거리가 maxL을 초과하면 불가능하므로 바로 false를 반환합니다.

func를 위한 전처리로서 입력된 위치는 정렬을 해주었고 중복된 위치는 불필요하므로 unique로 제거했습니다. 그리고 func의 구현을 간결하게 하기 위해 임의로 위치 0을 추가했습니다.

이분탐색은 func(lo)는 false, func(hi)는 true라는 단정문을 만족하도록 하면서, lo와 hi가 1만큼 차이날 때까지 돌리고, 마지막으로 갱신된게 hi가 아니라 lo인 경우가 있으므로 답을 출력하기 전에 func(hi)를 한번 더 호출해서 첫번째 자른 위치를 갱신합니다.

입력 범위에 L도 포함되길래 입력이 L만 유일하게 들어오는 케이스가 엣지 케이스인가 싶어 검토해봤으나 문제 없었고, 연산 중에 오버플로가 발생할 만한 부분도 없는데 어떤 케이스에서 틀리는 건지 모르겠습니다.