이진 탐색 알고리즘
Q
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
A
이진 탐색 알고리즘 공부한 내용 중 실전 문제 떡볶이 떡 자르기와 동일한 유형이다. target이 될 값이 없을 때에는 def가 아니라 while과 if를 이용해서 풀자.
코드
n, m = map(int, input().split()) #정수 입력받기
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: #떡의 양이 충분한 경우, 시작점 옮기기
start = mid + 1
result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기에 result 기록
print(result)
