[이코테] 이진 탐색 실습문제 3번

떡볶이 떡 만들기 문제 풀이

N,M = list(map(int,sys.stdin.readline().split()))
array = list(map(int,sys.stdin.readline().split()))
start = 0
end = max(array)
mid = (start+end) // 2 
while start <=end:
    sum = 0
    mid = (start + end) // 2
    for x in array:
        if x > mid:
         sum = sum + (x - mid)

    if sum < M:
        end = mid - 1
    else:
        result = mid
        start = mid + 1 


print(result)

이진 탐색을 함으로써 데이터의 개수가 과하게 많은 경우 O(NlogN)으로 수행 시간을 빠르게 단축시켜줄 수 있다.

문제 예제에서 원하는 최솟값의 합이 6이었으므로,

sum이 M보다 크다는 말은 mid가 아직 최솟값에 도달하지 못했다는 소리이므로 start = mid +1

sum이 M보다 작다는 말은 mid가 최솟값이 될 수 있는 값보다 오버되었다는 소리이므로 end = mid - 1

이렇게 탐색을 반복해주다 보면 최솟값이 나오게 된다.

 

유의점

- 이진 탐색은 데이터 사이즈가 많이 크게 예시가 잡히면, 시간복잡도를 고려해서 풀라는 의미를 내포하고 있을 확률이 높으므로

문제에서 sample size를 얼마로 잡아주는지, 시간 메모리 체크하고 문제 풀기