# [이.취.코] Chap 7. 이진 탐색 - 떡볶이 떡 만들기

- Author: @mildsalmon
- Published: 2021-08-23
- Updated: 2021-08-29
- Source: http://blex.me/@mildsalmon/chap-7-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%96%A1%EB%B3%B6%EC%9D%B4-%EB%96%A1-%EB%A7%8C%EB%93%A4%EA%B8%B0
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 이진탐색, 떡볶이떡만들기

---

# 1. 떡볶이 떡 만들기

- 난이도
	- 중
- 풀이 시간
	- 40분
- 시간 제한
	- 2초
- 메모리 제한
	- 128MB

### A. 문제

떡볶이 떡을 만든다. 떡의 길이가 일정하지 않다. 한 봉지에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

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

손님이 요청한 총 길이가 M이면 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라.

##### a. 예를 들면. 

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

##### b. 입력 조건

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

##### c. 출력 조건

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

##### d. 테스트 케이스

- 입력 예시

	```

	4 6
	19 15 10 17

	```

- 출력 예시

	```

	15

	```
	
### B. 내 답안

```python

n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
  
array.sort(reverse=True)  
  
m2 = 0  
  
while(m > m2):  
    max_value = max(array)  
    for i in range(len(array)):  
        if array[i] == max_value:  
            array[i] = array[i] - 1  
	m2 = m2 + 1  
	# print("array : ", array)  
	# print("m2 : ", m2)  
result = max(array)  
  
print(result)

```

##### a. 회고

> 풀이

떡의 개수 N은 최대 100만개, 요청한 떡의 길이 M은 최대 20억개.
따라서 떡의 개수의 시간 복잡도는 O(nlogn), O(n), O(logn)여야 1초 안에 동작한다.
요청한 떡의 길이의 시간 복잡도는 O(logn)이 되어야 시간 제한 안에 동작한다.

다만, 이 문제를 이진 탐색으로 푸는 방법이 생각나지 않았다.
그래서 단순하게 풀었는데, 내가 푼 방식의 시간 복잡도는 O(4m) 이다. 내 방식은 m에 의해 결정되므로 O(logm)이어야 시간 제한 안에 풀 수 있지만, 그러지 못했다.

> 반성

떡의 길이에 이진 탐색을 적용할 수 있다고 생각하지 못했다.

이진 탐색을 제대로 구현하는 부분도 아직 많이 부족하다고 느낀다.

### C. 문제 해설

이진 탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. **원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제**에 주로 파라메트릭 서치를 사용한다.

최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 코딩테스트나 프로그래밍 대회에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.

이 문제의 풀이 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이다. **현재 이 높이를 자르면 조건을 만족할 수 있는가?** 를 확인한 뒤에 조건의 만족 여부에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나간다.

절단기의 높이는 1부터 10억까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연하다는듯이 가장 먼저 이진 탐색을 떠올려야 한다.

높이 H를 이진 탐색으로 찾는다면, 대략 31번 만에 경우의 수를 모두 고려할 수 있다. 떡의 개수 N은 최대 100만 개이므로 이진 탐색으로 절단기의 높이 H를 바꾸면서, 바꿀 때마다 모든 떡을 체크하는 경우 대략 최대 3,000만 번 정도의 연산으로 문제를 풀 수 있다.

문제의 시간 제한은 2초이므로 3,000만 번 정도의 연산이 필요하다면 시간 초과를 받지 않을 수 있다.

![](https://static.blex.me/images/content/2021/8/23/9_bzoeDhE6PrILaZWmguAz.jpg)

##### a. 책 답안

[python-for-coding-test/8.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/7/8.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #이진탐색 #떡볶이떡만들기