이진 탐색 (Binary Search) (3) - 실전문제 7.3) 떡볶이 떡 만들기

문제)

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이 (H) 를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 

예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력 조건)

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

출력 조건)

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

입력 예시)

4 6
19 15 10 17

출력 예시)

15

---

해당 문제는 처음에 입력받은 배열 중 최댓값부터 시작해서 1씩 높이를 낮춰가면서 규칙을 찾아서 해결하려고 해봤다. 하지만 데이터의 개수와 크기가 매우 크므로 그런 방법으로는 시간 제한을 맞출 수 없다는 것을 깨달았고, 책을 참고하여 힌트를 얻었다. 바로 이진 탐색의 방법이였는데 단순히 배열의 인덱스에 해당하는 값으로만 이진 탐색을 접근해서 해당 문제에 해결방법을 얻지 못했던 것과 달리 배열의 인덱스가 아닌 시작점 = 0 (떡의 최소 길이), 끝점 = (입력받은 데이터 중 떡의 최대 길이) 로 이진 탐색을 하는 것이였다.

즉, 입출력 예시를 가정하면 시작점 = 0, 끝점 = 19로 이진 탐색을 시작한다. 이 때 중간점 = (0 + 19) // 2 = 9가 된다. 입력받은 떡의 길이 중 중간점 보다 작거나 같은 떡을 제외하고 긴 떡을 자른 길이만큼 더해서 합을 구한다.

• 합 > 원하는 떡 길이 : 최선의 방법이 아닐 수 있으므로 이진 탐색을 계속 진행하는데 이 때 최선의 방법인 가능성 때문에 이때의 중간값을 따로 저장
• 합 < 원하는 떡 길이 : 가능한 방법이 아니므로 이진 탐색 계속 진행
• 합 = 원하는 떡 길이 : 최선의 방법

이진 탐색의 과정은 아래와 같다. result는 중간값을 따로 저장하는 변수이다.

1. 중간점 = 9 / 자른 떡의 합계 = 25 => 원하는 떡 길이보다 크므로 다시 이진 탐색, result = 9

2. 중간점 = 14 / 자른 떡의 합계 = 9 => 원하는 떡 길이보다 크므로 다시 이진 탐색, result = 14

3. 중간점 = 17 / 자른 떡의 합계 = 2 => 원하는 떡 길이보다 작으므로 다시 이진 탐색

4. 중간점 = 15 / 자른 떡의 합계 = 6 => 원하는 떡 길이와 동일, result = 15

즉 출력 예시와 같이 15라는 결과를 얻을 수 있는 것이다. 소스코드는 아래와 같다.