Python 81 - 이진탐색 실전문제 2("떡볶이 떡 만들기")

난이도 ●●○    l    풀이 시간 40분    l    시간 제한 1초    l    메모리 제한 128MB    l

문제 

오늘 태영이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 태영이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이(H)를 지정하면 줄 지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 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 이다.

출력조건

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

문제해설

전형적인 이진 탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.        ((*결정 문제란 '예' 혹은 '아니오' 로 답하는 문제를 가리킨다.))

'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제' 에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 코딩 테스트나 프로그래밍 대회에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.

 

이 문제의 풀이 아이디어는 의외로 간단한데 적절한 높이를 찾을 때 까지 절단기의 높이 H를 반복해서 조정하는 것이다. 그래서 '현재 이 높이로 자르면 조건을 만족할 수 있는가?' 를 확인한 뒤에 조건의 만족 여부 ('예' 혹은 '아니오') 에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀나간다.

 

절단기의 높이(탐색 범위)는 1부터 10억까지의 정수중 하나인데, 이처럼 큰 수를 보면 당연하다는듯이 가장 먼저 이진 탐색을 떠올려야 한다. 이 문제에서 절단기의 높이 범위가 한정적이었다면 순차 탐색으로도 해결할 수 있지만, 현재 문제에서 절단기의 높이는 최대 10억까지의 정수이므로 순차 탐색은 분명 시간 초과를 받을 것이다.

반면에 높이 H를 이진 탐색으로 찾는다면, 대략 31번 만에 경우의 수를 모두 고려할 수 있다. 이때 떡의 개수 N이 최대 100만개 이므로 이진 탐색으로 절단기의 높이를 H로 바꾸면서, 바꿀때마다 모든 떡을 체크하는 경우 대략 최대 3,000만 번 정도의 연산으로 문제를 풀 수 있다.

 

문제의 시간 제한은 2초이므로 최악의 경우 3,000만 번 정도의 연산이 필요하다면 아슬아슬하게 시간 초과를 받지 않고 정답판정을 받을 것이다. 그렇다면 구체적으로 어떻게 이 문제를 이진 탐색으로 해결할 수 있을까? 절단기의 적절한 높이 H를 정하는 과정을 살펴보자.

 

다음의 예시를 살펴보자. 필요한 떡의 길이가 6cm이고, 떡의 높이가 차례대로 19, 15, 10, 17cm 이다. (이후 cm는 생략한다). 당연하지만, 절단기의 높이 H는 0부터 가장 긴 떡의 길이 안에 있어야만 떡을 자를 수 있다.

시작점 15

[ step2 ] 에서의 중간점에 1을 더한 값인 15로 설정한다. 이미 이전 단게에서 14 (중간점)인 경우를 처리했으므로 이번 단계에서는 15부터 본다는 의미이다.

이러한 이진 탐색 과정을 반복하면 답을 도출할 수 있다. 중간점의 값은 시간이 지날수록 '최적화된 값'을 찾기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 결과값을 중간점(MID) 값으로 갱신해주면 된다.

또한 이 문제에서는 현재 얻을 수 있는 떡볶이의 양에 따라서 자를 위치를 결정해야 하기 때문에 이를 재귀적으로 구현하는 것은 귀찮은 작업이 될 수 있다. 따라서 일반적으로 이 문제와 같은 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있다.

전체 소스코드는 다음과 같다.

답안예시

# 떡의 개수(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)

 

 

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding