[이진 탐색] 이코테 (파이썬) 떡볶이 떡 만들기 풀이

[문제]

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다.

 

동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는

 

절단기로 잘라서 맞춰줍니다.

 

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

 

낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면

 

자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다.

 

손님은 6cm만큼의 길이를 가져갑니다.

 

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의

 

최댓값을 구하는 프로그램을 작성하세요.

 

[입력 조건]

1. 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어집니다. (1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)

 

2. 둘째 줄에는 떡의 개별 높이가 주어집니다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼

 

    떡을 사갈 수 있습니다. 높이는 10억보다 작거나 같은 양의 정수 또는 0 입니다.

 

[출력 조건]

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

<입력 예시>
4 6
19 15 10 17
<출력 예시>
15

 

[풀이]

n, m = list(map(int, input().split()))

arr = list(map(int, input().split()))

start = 0
end = max(arr)

result = 0
while(start <= end) :
  total = 0
  mid = (start+end) // 2
  for x in arr :
    if x > mid :
      total += x - mid
  
  if total < m :
    end = mid - 1
  else :
    result = mid
    start = mid + 1

print(result)

 

먼저 떡의 개수(n)과 요청한 떡의 길이(m)을 입력받고 각 떡의 개별 높이 정보를 의미하는 arr 또한 입력받는다.

 

그리고 시작점(start)와 끝점(end)를 설정해주고 이진 탐색을 수행한다.

 

이진 탐색을 수행할 때는 반복문을 사용하며, 해당 범위를 반으로 나눠 변수 mid에 할당해 준 뒤

 

for문을 통해 떡을 잘랐을 때 떡의 양을 누적해가며 계산한다.

 

만약 떡의 양이 부족한 경우, 중간점을 기준으로 왼쪽 부분을 탐색하여 더 많이 자를 수 있도록 하고

 

만약 떡의 양이 충분한 경우, 중간점을 기준으로 오른쪽 부분을 탐색하여 덜 자를 수 있도록 한다.

 

또한, 최대한 덜 잘랐을 때가 정답이므로, else 내부에 변수 result 에 중간점 값을 할당해주고 최종적으로 해당 값을 출력한다.

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저