이진탐색 - 예제) 떡볶이 떡 만들기
💬 문제 이해
핵심) 절단기에 설정할 수 있는 높이의 최댓값을 구하시오
적어도 합쳐서 M만큼의 썰린 떡을 얻어야한다.
- 첫줄에 떡의 갯수 N과 요청한 떡의 길이 M이 주어진다
(1<=N<=1,000,000 1<=M<=2,000,000,000) - 둘째줄에 떡의 개별높이가 주어진다. (0<=높이<=10억)
발그림 ㅈㅅ 어차피 내가 이해하려고 그린거임
전형적인 이진탐색 문제이다 뭐??
🔍 Parametric Search
최적화 문제를 결정문제(yes or no)로 바꾸어 해결하는 기법
'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제' 에 주로 사용
ex) 범위 내에서 조건을 만족하는가장 큰 값 찾는 최적화 문제 등
➡️ 이진탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
코테에서 보통 parametric search는 이진탐색을 이용하여 해결
💡 문제 풀이 아이디어
"적절한 높이를 찾을때까지 절단기 높이 H를 반복해서 조정하는 것"
절단기의 높이는 1부터 10억까지인데
이렇게 노답으로 큰 수를 보면 가장먼저 이진탐색을 떠올려야한다.
시간복잡도 검증
높이H 찾기 : 대략 31번
떡의갯수 N이 최대 100만개이므로 바꿀때마다 모든 떡 체크 : 31*100만 =대략 최대 3,000만번 연산
문제 시간제한은 2초이므로, 아슬아슬하게 시간초과 받지 않고 정답!
코드
# 떡의갯수 n, 요청한 떡의 길이 m
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별높이 정보 array
array = list(map(int(input().split())))
# 이진탐색을 위한 시작점, 끝점
start = 0
end = max(array)
# 이진탐색 수행
result = 0
while (start <= end) :
total =0
mid = (start + end) // 2
for x in array :
# 잘랐을때의 떡 양 계산
if x > mid :
total += x - mid
# 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
if total < m :
end = mid - 1
# 떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
else :
result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
print(result)
Author And Source
이 문제에 관하여(이진탐색 - 예제) 떡볶이 떡 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yesterdaykite/7.-이진탐색-예제-떡볶이-떡-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)