[8/15] 떡볶이 떡 만들기

201 (실패)

내 코드 (실패)

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

def bs(array, target, start, end):
    
    while (start <= end):
        
        half = (start + end) // 2
        
        kal = array[half]
        hap = 0
        
        for i in range(len(array)):
            dduk = array[i] - kal
            if (dduk > 0):
                hap = hap + dduk

        if (hap == target):
            return kal
        elif (hap > target):
            start = half + 1
        else:
            end = half - 1
        
result = bs(arr, m, 0, n-1)
print(result)            

로직

이진 탐색으로 풀었지만, 범위 설정을 잘못해서 돌아가지 않는 코드이다.


효율적인 코드

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

start = 0
end = max(arr)

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
        start = mid + 1
        
print(result)

피드백

result에 값을 저장해두고, 자르는 길이를 늘렸을 때 맞지 않으면 그 값을 반환한다.

좋은 웹페이지 즐겨찾기