지금까지 푼 문제 중에서 처음 시도하고 가장 오랜만에 푼 문제다. 2020년 9월에 PS처음 시작해서 이분 탐색이 뭔지도 모르는데 대회 기출 문제에 있길래 무작정 박치기만 했었다. 그러고 나서 잊고 지냈었는데 최근에 이분 탐색 공부하면서 이 문제랑 비슷한 문제를 풀게 되었고, 이 문제도 덤으로 딸려오게 되었다.
당시에 아무리 고민해도 안 풀리니까 알고리즘 분류에 이분 탐색을 보게 되었는데 이분 탐색이 뭔지도 잘 몰랐었기 때문에 이거 보고 "전체 구간을 절반씩 나눠가면서 보는건가?"로 생각해서 분할 정복으로 계속 머리만 싸맸었다...
힌트 1)에서 처럼 이 문제를 푸는데 그리디한 해법은 찾기 힘든 것 같다. 결국 단순하게 모든 경우의 수를 시도해보아야 하는데... 을 가장 작은 조각의 길이가 가 되도록 개의 조각으로 나눌 수 있는지를 의미하는 함수로 정의하고 가능한 조각의 길이에 대해서 모두 시도해보면 가능할 것 같다. 왜냐하면 함수 는 단조증가하기 때문에 이분 탐색이 가능하기 때문이다.
함수 은 어떻게 구현할 수 있을까? 당연히 개의 조각으로 나누는 경우의 수를 모두 시도할 수는 없고, 자르는 순서는 상관이 없으므로 왼쪽부터 오른쪽으로 자른다고 가정하자.
우선 우리가 확인해야하는 것은 자를 수 있는 지점마다 자를 것인지, 자르지 않을 것인지 확인하는 일인데 자를 때 마다 조각은 한개씩 늘어나게 된다. 가장 작은 조각의 길이가 최대한 커지려면, 현재 위치를 잘라서 새로 만들어지는 조각의 길이가 를 넘기만 하면 바로 잘라야 한다.
기타 레슨 풀이에서의 증명과 비슷하게 증명할 수 있다.
import sys
input = sys.stdin.readline
print = sys.stdout.write
N, M, L = map(int, input().split())
S = [int(input()) for i in range(M)]
MIN = min(S[0], L - S[M - 1])
for i in range(1, M) :
MIN = min(MIN, S[i] - S[i - 1])
MAX = 0
for i in range(M) :
MAX = max(MAX, max(S[i], L - S[i]))
MAX += 1
Q = [int(input()) for i in range(N)]
# 롤케이크의 가장 작은 조각의 길이가 x이상이 되게
# q개의 조각으로 자를 수 있는지 여부
def f(x, q):
i = 0
prev = 0
while i < M and q:
if S[i] - prev >= x:
prev = S[i]
q -= 1
i += 1
# 마지막에 남은 조각의 길이도 확인해 줘야 한다.
return q == 0 and L - prev >= x
for q in Q:
lo = MIN
hi = MAX
# f(lo) == true 이고, f(hi) == false인 lo반환
while lo + 1 < hi:
mid = (lo + hi) // 2
if f(mid, q) : lo = mid
else : hi = mid
print(str(lo))
print("\n")
개의 자르는 횟수들에 대해서 가장 작은 조각 길이의 최댓값의 범위는 이고, 의 시간 복잡도는 이기 때문에
이 된다.