[이진 탐색] 떡볶이 떡 만들기 (실전문제, 이것이 코딩테스트다 with 파이썬)

문제

해설

전형적인 이진 탐색 & 파라메트릭 서치(Parametric Search) 유형의 문제

• 절단기 높이(탐색 범위)는 1부터 10억까지 정수 → 이진 탐색(순차 탐색은 시간 초과)

* 파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제(yes or no)로 바꾸어 해결하는 기법
• '원하는 조건을 만족하는 가장 알맞은 값 찾는 문제'에 주로 사용
  ex) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제 → 이진 탐색으로 결정 문제 해결하며 범위 좁힘

* 풀이 아이디어

• 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정
• '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인
• 조건의 만족 여부(yes or no)에 따라서 탐색 범위 좁혀서 해결

• 이진 탐색을 반복하여 답을 도출
• 중간점의 값은 시간이 지날수록 '최적화된 값'을 찾음
• 과정을 반복하면서 '잘린 떡 길이'가 '필요한 떡 길이'보다 크거나 같을 때마다 결괏값을 중간점(MID) 값으로 갱신
• 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고, 반복문을 이용해 구현하면 더 간결

 

풀이

# 변수 : N 떡의 개수, M 요청 떡 길이, array 개별 떡 높이
# 떡의 개수(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 요청 떡 길이, array 개별 떡 높이

 

1. N 떡의 개수, M 요청 떡 길이, array 개별 떡 높이 입력받기

2. 이진 탐색을 위한 시작점, 끝점 설정

----------- 이진 탐색 -----------

ㄴ 반복문, start > end 이면 종료

3. 중간점을 구함

4. 잘린 떡의 길이 계산 : 반복문, array[x] - 중간점

5. 시작점 or 끝점 업데이트

ㄴ 떡의 양 부족 : 왼쪽 부분 탐색

ㄴ 떡의 양 충분 : 정답 업데이트, 오른쪽 부분 탐색

------------------------------------

6. 정답 출력