떡볶이 떡 만들기

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

확인해야할 점

떡의 개수는 최대 1,000,000개, 요청한 떡의 길이 2,000,000,000 그리고 떡의 개별 높이는 1,000,000,000이다. 10억의 수를 탐색하기 위해서는 이분탐색을 사용해야한다.

풀이 방법

이분 탐색을 이용하는데, 인덱스를 이용하지 말고 값을 이용하자. 이분 탐색을 진행하기 위해서는 start, end를 정해야 한다. 인덱스를 사용하지 않고 값을 사용하니 start는 떡의 길이의 최소값인 0이 되고, end는 떡 배열의 최대값을 이용하면 된다. 그런 다음 이분 탐색을 진행하는데, start와 end를 통해 자를 지점인 mid를 구할 수 있다. mid값을 이용해서 떡을 자르고 M이 mid 절단 위치를 통해 자른 떡의 총길이보다 크면 end를 mid - 1로 설정하고, 작거나 같으면 start를 mid + 1로 설정해서 탐색한다.

소스코드

import sys

def binarySearch(start, end):
    result = 0  # 떡의 절단 길이 정하는 변수
    while start <= end:  # start가 end보다 작거나 같을 때까지
        total = 0  # 떡의 자른길이 변수
        mid = (start + end) // 2  # 중간값 저장하는 변수
        for item in array:
            if item > mid:  # item이 mid보다 크면 짤림
                total += item - mid  # 차이값 저장
        if total < M:  # 자른 떡의 총합이 M보다 작은 경우
            end = mid - 1  # 떡의 절단 마지막 위치를 mid 앞으로 위치 조정
        else:  # 자른 떡의 총합이 M보다 작거나 같은 경우
            result = mid  # 떡의 절단 길이 최신화
            start = mid + 1  # 떡의 절단 시작 위치를 mid 뒤로 위치 조정
    return result


N, M = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))

print(binarySearch(0, max(array)))  # 떡의 첫번째 길이부터 최대 길이까지 전달