from bisect import *
def cutting(l):
i = 0; MAX = 0
for _ in range(C):
idx = bisect(cut,l+cut[i])-1
MAX,i = max(MAX,cut[idx]-cut[i]),idx
return max(MAX,L-cut[i]),L-cut[i]
L,K,C = map(int,input().split())
cut = [0]+sorted({*map(lambda x:L-int(x),input().split())})
l,c,M,x = 1<<30,29,L,L
while 1:
M1,x1 = cutting(l)
if M>=M1:
if M==M1:
x = min(x,x1)
else:
x = x1
M = M1
if c==-1:
break
l -= 1<<c
else:
if c==-1:
break
l += 1<<c
c -= 1
print(M,x)이분탐색으로 구현하였다.
오랫동안 풀지 못했던 문제였다. 문제 자체는 단순해 보이는데, 입력의 불친절부터 시작해서 다양한 반례들, 처음 자르는 위치가 작은것을 찾는 방법 등 여러가지로 골치아팠던 문제
풀이를 설명하면,
1. 자르는 위치를 반대로 뒤집어서 정렬한다. (입력값이 x면 L-x로 입력받는다)
2. 매개변수를 l로 두고, l보다 작으면서 가장 큰 위치에 C번 자르면서 조각의 최댓값과 C번 자르고 남은 조각의 길이를 저장한다.
3. l을 이분탐색을 통해 늘리고 줄여가면서 계산한다. 조각의 최댓값을 작아지도록 갱신해주고, 조각의 최댓값이 같으면 남은 조각의 길이를 작아지도록으로 갱신해준다.
4. 1에서 입력값을 반대로 뒤집었기 때문에 남은 조각의 길이가 곧 가장 처음 조각의 길이이다. 조각의 최댓값과 가장 처음 조각의 길이를 출력한다.
가장 긴 조각의 길이를 찾는것은 어렵지 않겠지만 처음 자르는 위치를 작게 만드는 방식을 어떻게 구현해야 할지 떠올리기 어려웠다.
오늘의 교훈) 매개 변수 탐색과 이분 탐색을 적절하게 잘 활용하자