동빈이네 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어 가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기에 높이( H
)를 지정하면 줄지어진 떡을 한 번에 절단한다.
H
보다 긴 떡은 H
위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다.
잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다.
손님은 6cm만큼의 길이를 가져간다.
M
일 때 적어도 M
만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.입력조건
첫째 줄에 떡의 개수 N
과 요청한 떡의 길이 M
이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 떡의 개별 높이가 주어진다.
떡 높이의 총합은 항상 M
이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다.
높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
출력조건
M
만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
n, m = list(map(int, input().split(' ')))
array = list(map(int, input().split()))
start = 0
end = max(array)
result = 0
while(start <= end):
total = 0
mid = (start + end) // 2
for x in array:
#잘랐을 때 떡의 양 계산
if x > mid:
total += x - mid
#떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 탐색)
if total < m:
end = mid - 1
#떡의 양이 충분한 경우 덜 자르기(오른쪽 탐색)
else:
result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기에서 result 기록
start = mid + 1
print(result)
파라메트릭 서치
: 최적화 문제를 결정 문제('예' 혹은 '아니오'로 답하는 문제)로 바꾸어 해결하는 기법
'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다.
보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.
이 문제의 풀이 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이 H
를 반복해서 조정하는 것이다.
절단기의 높이 (탐색 범위)는 1부터 10억까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연하다는 듯이 가장 먼저 이진 탐색을 떠올려야 한다.
높이 H
를 이진 탐색을 찾는다면, 대략 31번 만에 경우의 수를 모두 고려할 수 있다.
N
이 최대 100만 개이므로 이진 탐색으로 절단기의 높이 H
를 바꾸면서, 바꿀 때마다 모든 떡을 체크하는 경우 대략 최대 3,000만 번 정도의 연산으로 문제를 풀 수 있다.<절단기의 적절한 높이 H
를 정하는 과정>
이러한 이진 탐색 과정을 반복하면 답을 도출할 수 있다.
mid
) 값으로 갱신해주면 된다.현재 얻을 수 있는 떡볶이의 양에 따라서 자를 위치를 결정해야 하기 때문에 이를 재귀적으로 구현하는 것은 귀찮은 작업이 될 수 있다.