문제
상근이는 나무 M미터가 필요하다.
목재절단기의 높이 H를 지정하면 톱날이 땅으로 부터 H미터 만큼
위로 올라간 다음, 한 줄에 연속해 있는 나무를 모두 절단해 버린다.
따라서 높이가 H보다 큰 나무는 H 위 부분이 잘릴 것이고,
낮은 나무는 잘리지 않을 것이다. 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이가 적어도 M미터의 나무를 집으로 가져가기 위해서 절단기에
설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.
둘째 줄에는 나무의 높이가 주어진다.
나무 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
기본 ver. binary_serch
x == a[q]
x > a[q]
x < a[q]
최인접수를 찾기 위한 binary_search
“적어도 x를 만족하는 최소(최대)값”이 의미하는 바는 다음 두 가지 중 하나이다.
1. x와 같다
2. x보다 크면서 가장 작은(큰) 값
예시로 a = [1,3,5,7,9,10]에서 8의 최인접수(큰쪽)를 찾아 보도록 하자.
결과 인덱스에 해당하는 값은
8 (a[q]==8) 또는
바로 이전 값은 8보다 작고 해당 값은 8보다 큰 수 (a[q-1]<8<a[q])
두 조건을 종합하면 리스트 a에서 x의 최인접수(큰쪽)을 찾기 위해서는
a[q-1] < x <= a[q]를 만족하는 q를 찾아야 한다.
# 최인접수(큰쪽)을 찾기 위한 binary_search
a = [1,3,5,7,9,10]
def binary_search(x,p,r):
q = (p+r)//2
if a[q-1] < x and x <= a[q]: return q
elif x > a[q]: return binary_search(x,q+1,r)
else: return binary_search(x,p,q-1)
print(a[binary_search(8,0,len(a))]) # 9
풀이
def binary_search(x,p,r):
def cutting(a,h):
m = 0
for x in a:
if x <= h: continue
m += (x-h)
return m
q = (p+r)//2
if cutting(a,q+1) < x and x <= cutting(a,q): return q
elif x > cutting(a,q): return binary_search(x,p,q-1)
else: return binary_search(x,q+1,r)
import sys
n, m = map(int,sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
print(binary_search(m,0,sum(a)))