[이것이코딩테스트] 떡볶이 떡 만들기

1. 문제 

- 각 길이가 일정하지 않은 떡들을 자르기 위해, 절단기에 높이 H를 지정하면 줄지어진 떡들이 한번에 절단된다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 손님은 H 위 부분의 길이만큼 가져간다. 손님이 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라

- 첫째 줄에 떡의 개수 N과 요청한 떡 길이 M이 주어지고, 둘째 줄에서는 떡의 개별 높이가 주어진다.

( N은 100만 이하, M은 20억 이하, H는 10억 이하)

 

2. 풀이 과정

- 읽다가 떡볶이 시킨 문제이다

- 구해야 할 것 : 최소 M만큼의 떡을 얻기 위해 필요한 절단기의 최대 높이

- 적어도 M만큼의 떡을 얻기위해 설정할 수 있는 높이의 최솟값 : 1 

- 최선의 상황에서 높이의 최댓값: 가장 긴 떡의 높이 - 1 ( M = 1인경우)

- 최소 ~ 최대 범위가 주어졌으며, N의 범위가 100만 이하이므로, 이분 탐색을 사용해보기

 

3. 새로 안 것 & 실수한 것

- 이분탐색 풀 때 min, max 등의 변수로 쓰지 않게 조심하거나, start, end로 해도 좋을 것 같다.

 

4. 코드

N,M = map(int,input().split())
array = list(map(int,input().split()))

min_height = 1
max_height = max(array) - 1
answer = 0

while min_height <= max_height:
	mid = int((min_height + max_height) / 2)
	temp_sum = 0
	for x in array:
		if x > mid:
			temp_sum += ( x - mid )
	if temp_sum >= M:
		answer = max(mid,answer)
		min_height = mid + 1
	else:
		max_height = mid - 1

print(answer)