[이진 탐색 알고리즘] 떡볶이 떡 만들기 - 파이썬(python)

떡볶이 떡 만들기

난이도 : 中 풀이 시간 : 40분

시간 제한 : 2초 메모리 제한 : 128 MB

 

---

 

해답

 

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

start, end = 0, max(ddeoks)
result = 0

while start <= end:
    total = 0

    mid = (start + end) // 2

    for i in ddeoks:
        if i > mid:
            total += i - mid

    if total < m:
        end = mid - 1
        
    else:
        result = mid
        start = mid + 1

print(result)

---

예시

 

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행 (반복적)
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 # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

# 정답 출력
print(result)

---

해설

 

n, m, ddeoks에 입력을 넣어줍니다. start와 end 변수를 선언해 시작점과 끝점을 지정해줍니다.
while 반복문 내에서 mid값보다 큰 떡들의 합을 total에 저장하고, 이를 비교하며 이진 탐색을 실행합니다.
total이 m보다 작을 경우, 중간값을 하나 낮춥니다. 이를 계속 반복합니다.
만약 total이 m보다 커지는 경우가 오면, result 변수에 현재 중간값을 저장합니다. 그리고 시작값을 중간값+1로 설정합니다.
위와 같은 과정을 통해 result 값을 구할 수 있고, 이를 print() 함수로 출력해주면 됩니다.