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

떡볶이 떡 만들기

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

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

 

---

 

해답

 

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

start, end = 0, max(array)

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

    for i in array:
        if i > mid:
            total = 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)

---

해설

 

전형적인 이진 탐색 문제이자 파라메트릭 서치 유형의 문제입니다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법입니다. 코딩 테스트에서 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결합니다.
풀이 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이를 반복해서 조정하는 것입니다.