Question
오늘은 떡볶이 떡을 만드는 날이다. 떡볶이 떡의 길이가 일정하지 않다. 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춘다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H대로 잘릴 것이고, H보다 낮은 떡은 잘리지 않는다. 손님은 잘린 길이만큼의 떡을 가져간다. H는 1부터 10억까지의 정수 중 하나이다. 손님이 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 손님이 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라.
Solution
이진 탐색 문제이자, 파라메트릭 서치 유형의 문제이다.
피라메트릭 서치란?
최적화 문제를 결정 문제('예' 혹은 '아니오'로 답하는 문제)로 바꾸어 해결하는 기법이다. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용한다. (ex) 범위 내에서 조건을 만족하는 가장 큰 값을 찾아라.) 보통 피라메트릭 서치 유형은 이진 탐색을 반복문으로 구현하여 해결한다.
큰 수를 보면 가장 먼저 이진 탐색을 떠올려야 한다.
이 문제에선 H의 범위 1부터 10억까지를 탐색하여 적절한 H값을 찾아야한다.
적절한 높이를 찾을 때까지 절단기 높이 H를 반복해서 조정한다. '현재 이 높이로 자르면 조건을 만족하는가?'를 따져 조건의 만족 여부('예' 혹은 '아니오')에 따라 탐색 범위를 좁혀가며 해결한다.
시작점(start)은 0, 끝점(end)은 가장 긴 떡의 길이로 설정한다. 중간점(mid)을 H로 설정했을 때 얻을 수 있는 떡의 길이 합이 손님이 요청한 길이(target, 즉 M)와 동일할 때까지 이진 탐색을 수행하여 적절한 H를 찾는다. M보다 크면 시작점을 증가시키고, M보다 작으면 끝점을 감소시킨다.
Code
# 떡의 개수 N과 요청한 떡의 길이 M
n, m = list(map(int, input().split()))
# 떡의 개별 높이
height = list(map(int, input().split()))
start = 0
end = max(height)
result = 0
while(start <= end) :
total = 0
H = (start + end) // 2
for h in height :
if h > H :
total += h - H
if total < m :
end = H - 1
else :
start = H + 1
result = H # 최대한 덜 잘랐을 때가 정답
print(H)