떡볶이 떡 만들기

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

문제 내용

• 길이가 일정하지 않은 떡볶이 떡이 한 개 이상 있음
• 한 봉지에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춤
• 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단
• 높이가 H보다 긴 떡은 H 위의 부분이 잘리고, 낮은 떡은 잘리지 않음
• 손님은 떡의 잘린 부분을 가지고 감
• 손님이 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성

입력 조건

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

출력 조건

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

입력 예시

4 6
19 15 10 17

출력 예시

15

문제 해설

• 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제
• 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법, 결정 문제는 '예' 혹은 '아니오'로 답하는 문제를 말함
• '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용
• 코딩 테스트에서 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결
• 이 문제의 풀이 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것
• '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부('예' 혹은 '아니오')에 따라서 탐색 범위를 좁혀서 해결할 수 있음
• 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나감
• 절단기의 높이가 1부터 10억까지이기 때문에 순차 탐색으로는 시간 초과가 됨
• 높이 H를 이진 탐색으로 찾는다면, 대략 31번 만에 경우의 수를 모두 고려할 수 있음
• 높이 H를 이진 탐색으로 찾는 과정
  1. 시작점은 0, 끝점은 가장 긴 떡의 길이(19)로 설정, 절단기 높이 H를 시작점과 끝점의 중간점인 9로 설정, 얻을 수 있는 떡의 합은 $(10 + 6 + 1 + 8) = 25$
  2. 시작점을 10으로 옮김, 끝점은 여전히 19이므로 중간점은 14, 절단기 높이를 14로 설정하면 얻을 수 있는 떡의 합이 $(5 + 1 + 3) = 9$, 여전히 필요한 떡의 길이인 6보다 크기 때문에 시작점을 증가시킴
  3. 시작점은 15, 끝점은 19, 중간점이 17이면 얻을 수 있는 떡의 합은 2, 필요한 떡의 길이인 6보다 작기 때문에 끝점을 감소시킴
  4. 시작점은 15, 끝점은 16, 중간점이 15이므로 얻을 수 있는 떡의 합은 $(4 + 2) = 6$, 필요한 떡의 길이인 6과 동일
• 위와 같은 이진 탐색 과정을 반복하면 답을 도출할 수 있음
• 중간점의 값은 시간이 지날수록 '최적화된 값'을 찾기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 결괏값을 중간점 값으로 갱신
• 이 문제에서는 현재 얻을 수 있는 떡의 양에 따라서 자를 위치를 결정해야 하기 때문에 재귀적으로 구현하는 것이 더 복잡해짐
• 일반적으로 이 문제와 같은 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있음

소스 코드

# 떡의 개수(N)와 요청한 떡의 길이(M)를 입력받기
n, m = 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)