[이코테] 이진탐색 - 떡볶이 떡 만들기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명 

동빈이네 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어, 높이가 19, 14, 10, 17 cm인 떡이 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 그리고 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm가 된다. 이 때 손님은 잘린 떡의 길이의 총 합인 6cm의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오

입력조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다(1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.(0 <= H <= 10억)

출력조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

사고과정

• 이진탐색을 활용하자는 마인드로 가는데, '무엇'을 이진 탐색할지를 문제에서 골라내는 데 가장 어려웠던 것 같음. 주어진 입력 예시를 토대로 그림을 그리면서 분석해보다가 그 '무엇'이 바로 절단기의 높이가 될 후보들을 배열로 나열한 뒤 이것 중 최적의 '높이'를 이진탐색해야 한다고 생각함.
• 그리고 이진 탐색할 때, middle의 인덱스값에 따라 start, end 인덱스를 조정하는 판단은 바로 손님이 요청한 떡의 길이(M)과 절단기 높이로 짜르고 남은 떡의 길이 합과의 대소비교를 기준으로 하는 것이라는 생각함.
• 내 풀이에서 구현함. 하지만 부족한 점이 한 가지 있었음
• 나는 M과 짜르고 남은 떡의 길이 합이 같을 때와 클 때를 구분해서 나눔. 같을 때는 해당 길이가 최적의 높이라고 생각하고 리턴했지만 클 경우에는 클 때의 절단기 높이를 따로 리스트에 담고 이 중 가장 큰 절단기 높이를 리턴하도록 함
• 하지만 위 경우로 굳이 하지 않고 짜르고 남은 떡의 길이 합 >= M일 때를 한 번에 처리할 수 있었음(책 속 풀이에서). 왜냐하면 짜르고 난 뒤 떡의 길이 합 > M일 때, 계속 절단기 높이를 갱신하다 보면 결국에 이진탐색의 마지막은 적어도 M 길이보다 크면서 절단기의 높이가 가장 높은 값이라는 것이기 때문. 이 사실을 깨닫지 못해서 내 풀이에서 불필요한 코딩 줄이 추가됨.

풀이

1. 내가 푼 풀이

import sys

N, M = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
# 절단기 높이 후보들
heights = [h for h in range(array[0], array[-1] + 1)]


def binary_serach(heights, start, end):
    # 손님이 가져갈 떡 길이가 M보다 클 때의 절단기 높이를 담기위한 리스트
    result = []
    while start <= end:
        middle = (start + end) // 2
        dduk = 0
        for a in array:
            dduk += max(0, (a - heights[middle]))
        if dduk == M:
            return heights[middle]
        elif dduk < M:
            end = middle - 1
        elif dduk > M:
            result.append(heights[middle])
            start = middle + 1
    result.sort(reverse=True)
    return result[0]


start = 0
end = len(heights) - 1
res = binary_serach(heights, start, end)
print(res)

2. 책의 풀이

참고로, "범위 내에서 조건을 만족하는 가장 큰 값을 찾아!"라는 문제는 이진탐색으로 범위를 좁혀나가면서 최적의 값을 찾는 문제 유형이라고 함. 또 주어진 데이터가 억 단위의 큰 수라면 이진 탐색을 떠올려보라고 한다.

# 1. "범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제 -> 이진탐색으로 범위를 좁혀나가면서 최적의 값 찾기!
# 2. 억단위의 큰 수가 보이면 이진 탐색을 떠올리자!
n, m = map(int, input().split())
array = list(map(int, input().split()))

# 절단기 적절 높이를 찾기 위한 범위 설정
start = 0
end = max(array)

# 절단기 높이 갱신할 변수
result = 0
while start <= end:
    # 손님이 가져갈 떡의 길이 계산할 변수
    dduk = 0
    middle = (start + end) // 2
    for a in array:
        if a > middle:
            dduk += (a - middle)
    if dduk < m:
        end = middle - 1
    else:
        result = middle     # dduk m보다 값이 클수록 절단기 높이는 당연히 낮아짐.
        start = middle + 1  # 따라서 이진탐색 마지막의 result가 dduk이 m에 가장 근사하면서 절단기가 높을 때의 값이 됨!
print(result)