들어가며
이글은 동빈나님의 이코테 강의를 보며 정리한 글입니다.
Parametric Search
매개 변수 탐색(Parametric Search)란 최적화 문제를 결정 문제로 바꾸어 해결하는 기법입니다.
떡볶이 떡 예제
높이가 재각각인 떡볶이 떡이 있다고 하겠습니다. 손님이 떡의 양을 전달하면 떡을 잘라서 손님에게 전달해야 합니다. 이 떡들은 높이가 동일한 칼로 한번에 썰어낼 수 있습니다. 즉, 칼의 높이가 더 크면 떡은 썰리지 않을 것이고, 떡의 높이가 더 크면 떡이 썰리겠죠.
예를 들어서 떡의 길이가 각각 9, 4, 4, 5라고 했을 때, 높이가 4인 칼로 썰면 각각 5, 0, 0, 1의 떡이 절단되어 손님은 6만큼 얻을 수 있는겁니다.
이 상황에서 손님이 요구한 떡을 제공하기 위해서 설정할 수 있는 높이의 최댓값을 구해보겠습니다.
이러한 경우에서 사용할 수 있는 것이 바로 매개 변수 탐색입니다. 각각의 순간을 예, 아니오로 설정해서 최적값을 구하는 방법이죠.
손님이 3만큼의 떡을 원하는 경우 높이를 찾는 과정을 도시화해보겠습니다. 현재 떡의 상태입니다. 예시를 위해서 떡은 각각 9, 7, 4, 5의 길이를 갖고 있습니다.
여기서 가장 긴 떡의 길이는 9죠. 이 떡을 이용해서 이진탐색을 수행하여 높이를 설정하고 떡의 길이를 구해보겠습니다.
9인 떡의 시작점과 끝점은 각각 0과 9이고, 중간점은 공식에 의해서 4입니다. 이 상태에서는 손님이 원하는 양인 3을 만족합니다. 그래서 4라는 중간값을 기록하고, 떡의 양을 줄이면서 한번 더 이진탐색을 수행해보겠습니다.
자, 이번에는 떡의 양을 줄이기 위해서 오른쪽 영역으로 시작점과 끝점을 옮겼습니다. 역시나 잘린 떡의 양은 4이고, 이는 손님이 요구하는 3을 만족합니다. 그렇기 때문에 중간값을 기록하고, 오른쪽 영역을 한번 더 탐색하겠습니다.
자, 이번에는 떡의 양이 2입니다. 손님의 요구를 맞출 수 없기 때문에, 중간값은 기록하지 않고, 왼쪽 영역을 탐색합니다. 하지만, 왼쪽 영역이 이미 탐색할 수 없게 될만큼 줄어들었기 때문에 탐색을 종료합니다. 여기서 기록된 값중 가장 마지막 값을 출력하면 손님의 요구를 맞추면서 가장 최대로 높이를 설정할 수 있습니다. 이러한 과정을 코드로 나타내면 아래와 같습니다.
# 떡의 갯수와 떡의 길이 입력
n, m = list(map(int, input().split(' ')))
# 떡의 길이들 입력
arr = list(map(int, input().split()))
# 시작점과 끝점 설정
start = 0
end = max(arr)
# 이진 탐색이 불가능할때까지 수행
while(start <= end):
total = 0
mid = (start + end) // 2
for x in arr:
# 떡의 높이가 더 크다면 합산
if x > mid:
total += x - mid
# 떡의 양이 부족하다면 왼쪽 부분 탐색
if total < m:
end = mid - 1
# 떡의 양이 충분하다면 result에 저장 밑 오른쪽 부분 탐색
else:
result = total
start = mid + 1
# 정답 출력
print(result)시작점은 항상 0이지만, 끝점은 가장 긴떡을 사용해야 합니다. while 반복문을 이용해서 탐색이 가능할때까지 탐색을 반복하여 탐색이 종료되면 result를 출력해서 정답을 맞출 수 있습니다.
