[이진 탐색 알고리즘] ▲ 문제2 - 떡볶이 떡 만들기(201p)

[이코테] 문제2 - 떡볶이 떡 만들기(201p)

(한줄평) 탐색 범위를 보고 이진 탐색으로 풀어야함을 알아야 풀 수 있는 문제로 해결은 했지만 복습이 필요한 문제!

풀이 시간: 30분 이내

---

1) 문제 해결 아이디어

적절한 절단기 높이를 찾을 때까지 이진 탐색을 수행하여 높이 h를 반복해서 조정하면 된다.

"현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 뒤 조건의 만족 여부(예/아니오)에 따라서 탐색 범위를 좁혀서 해결할 수 있다.

절단기의 높이는 0이상 10억이하의 정수인데 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다!! 그렇지 않으면 시간초과가 날 것이다!

여기서 기억할 점은 절단기의 높이가 커질 수록 잘린 떡의 길이의 총합이 작아진다는 점이다.

 

<동작 과정>

1. 시작점: 0, 끝점: 입력받은 떡 높이들 중 최댓값 으로 설정

중간점: 현재 절단기 높이

2. 잘린 떡의 길이의 총합(length) 계산

3. 잘린 떡의 길이의 총합(length)와 필요한 떡의 길이(m) 비교

3-1. 잘린 떡의 길이의 총합(length)가 필요한 떡의 길이(m)보다 작다면, 

절단기 높이(mid)를 줄여야 하므로 끝점(end) 조정

3-2. 잘린 떡의 길이의 총합(length)가 필요한 떡의 길이(m)보다 크다면, 

절단기 높이(mid)를 늘려야 하므로 시작점(start) 조정 & 절단기 높이 최댓값(max_length) 갱신

 

Q. 3-2에서는 시작점 조정과 함께 절단기 높이 최댓값을 갱신하는 이유는?

이 문제에서는 단순하게 요청한 떡의 길이(m)이 되는 절단기 높이를 구하는 것이 아니라,

최소 떡의 길이(m)을 얻기 위한 절단기 높이의 최댓값을 구하는 것이다.

3-1조건일 때는 그냥 절단기 높이를 줄이기만 하면된다.

3-2조건일 때는 절단기 높이를 늘려야 한다. 하지만 현재로서는 그 높이가 최댓값인지는 알 수 없다. 그러므로 그 값을 저장해두어야 한다!!

 

2) 소스코드

# 이진 탐색
def binary_search(array, target, start, end):
  global max_length
  while True:
    # 시작점과 끝점이 엇갈리면 종료
    if start > end:  break
    mid = (start + end) // 2  # 절단기 높이
    length = 0    # 잘린 떡의 길이 총합
    # 잘린 떡의 길이 총합 계산하기
    for i in range(n):
      # 떡 높이가 절단기 높이보다 크다면
      if array[i] > mid:  length += array[i] - mid  
    
    # 1. 잘린 떡의 길이가 필요한 떡 길이보다 작다면
    if length < m:  
      end = mid - 1  # 절단기 높이 감소
    # 2. 잘린 떡의 길이가 필요한 떡 길이보다 크거나 같다면
    else:  
      start = mid + 1  # 절단기 높이 증가
      max_length = mid # 최댓값 갱신
      #print(max_length)  

n, m = map(int, input().split())  # 떡 개수, 떡 길이
array = list(map(int, input().split()))  # n개의 떡의 높이
max_length = 0  # 절단기 높이 최댓값
binary_search(array, m, 0, max(array))
print(max_length)