[이코테] CH07 이진 탐색 실전문제 3번 떡볶이 떡 만들기

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findMax():
    start = 0
    end = max(array)
    while start <= end:
        mid = (start + end) // 2
        sum = 0
        for i in range(len(array)):
            if array[i] > mid:
             sum += (array[i] - mid) # 떡이 잘리는 부분
        if sum == M:
           break
        elif sum > M:
         start = mid + 1
        else: 
         end = mid - 1  # 시작점을 늘려       
    return mid

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

푼 방법:

mid를 0과 최댓값의 사이로 잡고 시작 이후

만약 떡의 잘린 길이가 M보다 더 크면 더 잘라야 하므로 start = mid + 1

반대 상황에선 덜 잘라야 하므로 end = mid - 1

만약 딱 M이 되는 상황이 온다면 break

mid를 반환시켜주었다 ( 여기서 mid가 절단기의 기준으로 쓰임)

 

보통 코테에서는 단원명을 "이진 탐색 문제입니다" 주지 않는다

따라서.. 뭔가 단순 구현 O(N)으로 풀면 털린다는 것을 알아야 한다(문제에서 높이가 0과 10억의 범위, M값이 2,000,000,000까지의 범위를 줬으므로 

O(logN)으로 구현하지 않으면 절대 안된다는 것을 캐치해야 한다

여기서 이진 탐색을 통해 구현 범위를 반씩 좁혀나가며 최댓값을 찾는 것이 포인트