백준 케이크 자르기(17179)

케이크 자르기

지금까지 푼 문제 중에서 처음 시도하고 가장 오랜만에 푼 문제다. 2020년 9월에 PS처음 시작해서 이분 탐색이 뭔지도 모르는데 대회 기출 문제에 있길래 무작정 박치기만 했었다. 그러고 나서 잊고 지냈었는데 최근에 이분 탐색 공부하면서 이 문제랑 비슷한 문제를 풀게 되었고, 이 문제도 덤으로 딸려오게 되었다.
당시에 아무리 고민해도 안 풀리니까 알고리즘 분류에 이분 탐색을 보게 되었는데 이분 탐색이 뭔지도 잘 몰랐었기 때문에 이거 보고 "전체 구간을 절반씩 나눠가면서 보는건가?"로 생각해서 분할 정복으로 계속 머리만 싸맸었다...

1. 힌트

1) 가장 가운데에 있는 지점을 나누는 것이 최적해가 아니다. 그렇기 때문에 우리는 모든 경우를 시도해보아야 한다. 하지만 모든 자를 수 있는 지점에 대해서 자르는 방법을 모두 시도하는 것 또한 불가능하다.

2) 가장 작은 조각의 길이가 $x$이상이 되게 $m$개의 조각으로 자르는 방법에는 그리디한 해법이 존재한다.

3) $x$이상이 되게 가능하다면 당연히 $x - 1$이상이 되게 자르는 것도 가능하다. 이를 이용해 이분 탐색이 가능하다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

힌트 1)에서 처럼 이 문제를 푸는데 그리디한 해법은 찾기 힘든 것 같다. 결국 단순하게 모든 경우의 수를 시도해보아야 하는데... $f(x,\ m)$을 가장 작은 조각의 길이가 $x$가 되도록 $m$개의 조각으로 나눌 수 있는지를 의미하는 함수로 정의하고 가능한 조각의 길이에 대해서 모두 시도해보면 가능할 것 같다. 왜냐하면 함수 $f$는 단조증가하기 때문에 이분 탐색이 가능하기 때문이다.

9) 순서를 강제할 수 있을까?

함수 $f(x, \ m)$은 어떻게 구현할 수 있을까? 당연히 $m$개의 조각으로 나누는 경우의 수를 모두 시도할 수는 없고, 자르는 순서는 상관이 없으므로 왼쪽부터 오른쪽으로 자른다고 가정하자.
우선 우리가 확인해야하는 것은 자를 수 있는 지점마다 자를 것인지, 자르지 않을 것인지 확인하는 일인데 자를 때 마다 조각은 한개씩 늘어나게 된다. 가장 작은 조각의 길이가 최대한 커지려면, 현재 위치를 잘라서 새로 만들어지는 조각의 길이가 $x$를 넘기만 하면 바로 잘라야 한다.
기타 레슨 풀이에서의 증명과 비슷하게 증명할 수 있다.

3. 구현

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")

1) 시간 복잡도

$N$개의 자르는 횟수들에 대해서 가장 작은 조각 길이의 최댓값의 범위는 $O(L)$이고, $f$의 시간 복잡도는 $O(M)$이기 때문에
$O(N\times M\times lgL)$이 된다.

2) 테스트 케이스