[이취코] 떡볶이 떡 만들기 (Python)

처음에 짠 코드

import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

sorted_arr = sorted(arr)
end = sorted_arr[n-1] # 19
start = sorted_arr[0]


for i in range(end - 1, start, -1):
    count = 0
    for j in range(len(sorted_arr)):
        if sorted_arr[j] - i >= 0:
            count += sorted_arr[j] - i
    if count == m:
        break
print(i)

BS를 적용한 코드

n, m = list(map(int, input().split(' ')))
arr = list(map(int, input().split()))

end = max(arr) # 19
start = 0 # 10


result = 0
while start <= end:
    count = 0
    mid = (end + start) // 2

    for i in arr:
        if i > mid:
            count += i - mid
    if count < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

• 처음에 짠 코드는 밑도 끝도 없이 푼 느낌이라면 BS를 적용함으로서 확실히 수행 속도가 빨라지고, 체계적으로 문제를 풀어나갈 수 있었다.