[Algorithm] (이코테) 이진 탐색 - 떡볶이 떡 만들기 (Python/파이썬)

▶ 문제 설명

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

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

---

▶ Code

# 떡의 개수(N)와 요청한 떡의 길이(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)

▶ Point

• 전형적인 이진  탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 코딩 테스트나 프로그래밍 대회에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.
• 이 문제의 풀이 아이디어는 의외로 간단한데 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이다. 그래서 '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부('예' 혹은 '아니오')에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나간다.
• 절단기의 높이(탐색 범위)는 1부터 10억까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연하다는 듯이 가장 먼저 이진 탐색을 떠올려야 한다. 이 문제에서 절단기의 높이 범위가 한정적이었다면 순차 탐색으로도 해결할 수 있지만, 현재 문제에서 절단기의 높이는 최대 10억까지의 정수이므로 순차 탐색은 분명 시간 초과를 받을 것이다.
• 반면에 높이 H를 이진 탐색으로 찾는다면, 대략 31번 만에 경우의 수를 모두 고려할 수 있다. 이때 떡의 개수 N이 최대 100만 개이므로 이진 탐색으로 절단기의 높이 H를 바꾸면서, 바꿀 때마다 모든 떡을 체크하는 경우 대략 최대 3,000만 번 정도의 연산으로 문제를 풀 수 있다.
• 문제의 시간 제한은 2초이므로 최악의 경우 3,000만 번 정도의 연산이 필요하다면 아슬아슬하게 시간 초과를 받지 않고 정답 판정을 받을 것이다. 그렇다면 구체적으로 어떻게 이 문제를 이진 탐색으로 해결할 수 있을까? 절단기의 적절한 높이 H를 정하는 과정을 살펴보자.
• 다음의 예시를 살펴보자. 필요한 떡의 길이가 6cm이고, 떡의 높이가 차례대로 19, 15, 10, 17cm이다. (이후 cm는 생략한다.) 당연하지만, 절단기의 높이 H는 0부터 가장 긴 떡의 길이 안에 있어야만 떡을 자를 수 있다.
  
  <STEP 1> - 시작점은 0, 끝점은 가장 긴 떡의 길이 (19) 로 설정한다. 0과 19 사이의 중간점 9를 절단기 높이 H로 설정하면 얻을 수 있는 떡의 합은 (10 + 6 + 1 + 8) =25이다. 필요한 떡의 길이가 6보다 크기 때문에 시작점을 증가시킨다.
  
  <STEP 2> - 시작점을 10으로 옮긴다. 끝점은 여전히 19이므로 중간점은 14이다. 절단기 높이를 14로 설정하면 얻을 수 있는 떡의 합이 (5 + 1 + 3) = 9 이다. 여전히 필요한 떡의 길이인 6보다 크기 때문에 시작점을 증가시킨다.
  
  <STEP 3> - 현재 시작점은 15, 끝점은 19, 중간점이 17 이므로 얻을 수 있는 떡의 합은 2이다. 필요한 떡의 길이인 6보다 작기 때문에 끝점을 감소시킨다. (STEP 2 에서의 중간점에 1을 더한 값인 15로 설정한다. 이미 이전 단계에서 14(중간점)인 경우를 처리했으므로 이번 단계에서는 15부터 본다는 의미이다.)
  
  <STEP 4> - 현재 시작점은 15, 끝점은 16, 중간점이 15이므로 얻을 수 있는 떡의 합은 (4 + 2) = 6이다. 필요한 떡의 길이인 6과 동일하다. 
• 이러한 이진 탐색 과정을 반복하면 답을 도출할 수 있다. 중간점의 값은 시간이 지날수록 '최적화된 값'을 찾기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 결괏값을 중간점(MID) 값으로 갱신해주면 된다. 또한 이 문제에서는 현재 얻을 수 있는 떡볶이의 양에 따라서 자를 위치를 결정해야 하기 때문에 이를 재귀적으로 구현하는 것은 귀찮은 작업이 될 수 있다. 따라서 일반적으로 이 문제와 같은 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있다.