[Algorithm] Binary Search - ‘떡볶이 떡 만들기’

📣 학습한 내용을 정리한 글입니다.

이진탐색 알고리즘 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

영준이는 여행가신 부모님을 대신해서 떡집에서 일을 하기로 했다. 떡을 만드는 상황에서 떡의 길이는 각각 일정하지 않게 만든다.
한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기 높이(H)를 지정하면 만든 떡들을 한 번에 절단한다.
높이가 H보다 긴 떡은 H 위의 부분이 잘리고 낮은 떡은 잘리지 않는다.
이때 떡볶이 N개 중 손님이 요청한 총 길이가 M일때 절단기로 떡을 잘랐을 때,
적어도 M만큼의 떡을 얻기위해 절단기에 설정할 수 있는 높이 H의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1,000,000 / 1 <= M <= 2,000,000,000)
두 번째 줄에는 떡의 개별 높이가 입력된다. 이때 떡 길이의 총합은 항상 M 이상이다.

출력

첫째 줄에 문제에서 요구하는 상황에서의 높이 최댓값을 출력한다.

문제 풀이

---

Binary Search Algorithm 참고내용

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
  
• 일반적으로 Parametric Search 문제에 이진 탐색을 이용하여 해결할 수 있다.
  • Parametric Search : 최적화 문제를 결정문제(예 혹은 아니오)로 바꾸어 해결하는 기법
    

위 참고사항을 준수하며, 풀어보자.
적절한 높이를 찾을 때까지 이진 탐색을 이용하여 높이 H를 반복해서 조정한다.
현재 이 높이에서 자르면 조건을 만족할 수 있는가를 확인한 뒤에 조건의 만족 여부에 따라서 탐색 범위를 좁혀나간다.

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 5. 이진 탐색 영상

---