[이진탐색] 이진탐색 (5) 실전 문제 - 떡볶이 떡 만들기 ⭐

이코테 p.201 실전 문제 - 떡볶이 떡 만들기

입력 예시

4 6 19 15 10 17

출력 예시

15

내 소스코드

• 주어진 떡 길이 중에서 가장 긴 떡의 길이를 기준으로 1씩 감소시켜 가며 조건을 만족시키는지 확인하는 방식으로 구현함
  • ex) 가장 긴 떡이 19라면 18, 17, 16, ... 처럼 1씩 감소시켜 나가면서 해당 길이로 떡을 잘랐을 경우 조건을 만족하는지 확인
• 순차 탐색이라 데이터가 많을 수록 비효율적. 해당 문제에 적합하지 않음.

# 입력 받기
n, m = map(int, input().split())
array = list(map(int, input().split()))
array.sort()

# 이진 탐색을 통해 탐색 범위 좁기
def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return start, end
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return end, start

# 리스트의 최댓값 - 1 부터 순차적으로 조건을 만족하는 값 찾기
init = array[len(array) - 1] - 1
for i in range(init, 0, -1):
  # 이진 탐색으로 탐색 범위 구하기
  start, end = binary_search(array, init, 0, len(array) - 1)
  total = 0
  for j in range(start, end + 1):
    diff = array[j] - init
    if(diff > 0): # 떡의 길이가 목표 길이보다 긴 경우 자른 후 총합에 추가
      total += diff
    else:
      continue
  if total == m: # 자른 떡 길이의 총합이 m과 같으면 종료
    break
  else: # 자른 떡 길이의 총합이 m과 다르면 1 감소시킨 후 다시 탐색
    init -= 1

print(init)

교재 문제해설 & 소스코드

• 전형적인 이진 탐색 문제
• 파라메트릭 서치 유형
  • 최적화 문제를 결정문제(예 혹은 아니오로 답하는 문제)로 바꾸어 해결하는 기법
  • 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에서 주로 파라메트릭 서치 사용
  • ex) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀나갈 수 있음
  • 파라메트릭 서치 유형은 보통 이진 탐색으로 해결
• 풀이 아이디어 - 적절한 높이를 찾을 때까지 절단기 높이 H를 반복해서 조정
  • 현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 뒤, 조건의 만족 여부(예 혹은 아니오)에 따라서 탐색 범위를 좁혀나가며 해결
  • 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나감
  • 절단기의 높이(탐색 범위)는 1부터 10억까지의 정수이므로 이진 탐색 적용
• 절단기의 적절한 높이 H를 정하는 과정
  • 필요한 떡의 길이가 6cm이고, 떡의 높이가 차례대로 19, 15, 10, 17cm인 경우, 절단기의 높이 H는 0부터 가장 긴 떡의 길이, 즉 19까지 가능
    1. 시작점 0, 끝점 19, 중간점 9 ➡️ 떡의 합은 (10 + 6 + 1 + 8) = 25. 필요한 떡의 길이인 6보다 크므로 시작점 증가
    2. 시작점 10, 끝점 19, 중간점 14 ➡️ 떡의 합은 (5 + 1 + 3) = 9. 필요한 떡의 길이인 6보다 크므로 시작점 증가
    3. 시작점 15, 끝점 19, 중간점 17  ➡️ 떡의 합은 2. 필요한 떡의 길이인 6보다 작으므로 끝점 감소
    4. 시작점 15, 끝점 16, 중간점 15 ➡️ 떡의 합은 (4 + 2) = 6. 필요한 떡의 길이인 6과 동일
• 위와 같은 이진 탐색 과정을 반복하여 문제 해결 가능
• 조건을 만족하는 최대의 떡의 길이를 찾아야 하므로, 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 결과값을 중간점 값으로 업데이트

# 입력 받기
n, m = map(int, input().split())
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행 (반복문으로 현)
result = 0
while start <= end:
  mid = (start + end) // 2 # 중간점
  total = 0
  for i in array:
    # 잘랐을 때의 떡의 양 계산
    if i > mid:
      total += (i - mid)
  # 떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
  if total >= m:
    result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result를 업데이트
    start = mid + 1
  # 떡의 양이 부족한 경우 더 자르기 (왼쪽 부분 탐색)
  else:
    end = mid - 1

# 결과 력
print(result)