떡볶이 떡 만들기(p.201) - 이진 탐색(이코테)

---

해설 부분은 책의 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명 

 

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총길이는 절단기로 잘라서 맞춰준다. 

 

절단기의 높이(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만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다. 

 

입력 예시

 

4 6
19 15 10 17

 

출력 예시

 

15

 

 

 

---

 

 

문제 해설

 

저자는 이 문제를 전형적인 이진 탐색 문제이자, 파라메트릭 서치^{parametric search} 유형의 문제라고 했다. 파라메트릭 서치 문제란 '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 적용되는 해결기법이다. 이진 탐색의 아이디어로 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이 목적이다. 이 문제는 p.369의 공유기 설치 문제와 유사하다. 자, 그럼 책에서 제시한 해설 코드를 보도록 하자. 

 

# 떡의 개수와 요청한 떡의 길이 입력 
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가 원하는 m에 맞추어 자를 수 있는 최대 높이 값 
    mid = (start + end) // 2 
    for x in array: 
        # 잘랐을 때의 떡의 양 계산 
        if x > mid: 
            total += x - mid 
    # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색) 
    if total < m: 
        end = mid - 1 
    # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색) 
    else: 
        # 적어도 m만큼은 떡을 얻어야 해서 else일때 절단기 길이를 저장, 그 후 반복으로 최적값 찾음 
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록 
        start = mid + 1 
print(result)

 

함수로 만들어본 버전이다. 내용은 위의 코드와 같다. 

# 함수로 만들어본 경우 
def binary_search(array):
    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:
            start = mid + 1
            result = mid 
    return result 

n, m = map(int, input().split()) 
array = list(map(int, input().split())) 
print(binary_search(array))

 

 

start와 end를 무엇으로 설정했는지를 파악해야 한다. 여기선 떡볶이의 높이로 설정했다. 그래서 start와 end로 만드는 mid가 절단기의 높이가 되도록 설정한다. start는 가장 작은 값이어야 하기에 0으로 설정했고, end는 절단기의 높이의 최댓값이 가장 긴 떡이 길이가 되니 max(array)로 설정한다. 

 

처음 코드를 접하면 해설이 분명 어렵다. 필자도 그랬다. 하지만 반복문 for i in x: 부분은 앞 문제 '부품 조립'에서 비슷한 형태가 나왔고 result = mid를 저장하는 방식도 '공유기 설치' 문제에서 봤던 방식이다. 하나하나 코드를 이해해보자.

 

for x in array:
  if x > mid:
    total += (x - mid)

array에 저장된 떡의 길이를 x 라 할때 x가 mid(절단기의 높이) 보다 커야지 떡이 잘리게 된다. 그래서 if x > mid: 가 나오게 되고, 절단기에 의해 잘린 떡들을 (x - mid)로 표현해서 total 변수에 모두 저장해 준다. 절단기 보다 높이가 작은 떡들은 잘리지 않고 반복문의 차례를 넘기게 된다. 

 

if total >= m:
  result = mid
  start = mid + 1

 

만일 이렇게 모은 total이 원하는 길이인 m을 넘긴다면, 현재의 절단기의 높이(mid)를 result에 저장을 하고, 절단기 길이가 좀 짧은 거 같으니, 절단기 길이를 늘려서 떡을 조금 남기도록 start 값을 조정해야 한다. start 값을 조정하면, mid 값이 커지게 돼서 x - mid로 모아지는 total 값이 작아지게 되기 때문이다. 

 

else:
  end = mid - 1

 

모아진 떡의 양이 부족한 경우엔 end 를 조정해서 절단기의 높이를 낮게 함으로써 더 많은 떡이 모일 수 있도록 한다. 

 

이렇게 반복문을 수행하다 반복이 끝나면 최적의 절단기의 높이(mid)가 result에 저장되고 result를 출력하면 원하는 결과가 나오게 된다.