n, m = map(int, input().split())
T = list(map(int, input().split()))
def Bsearch(list, goal, lower, upper) :
if lower > upper :
return upper
sum = 0
center = (lower + upper) // 2
for i in list :
if i > center :
sum = sum + i - center
if sum == goal :
return center
if sum > goal :
return Bsearch(list, goal, center + 1, upper)
else :
return Bsearch(list, goal, lower, center -1)
print(Bsearch(T, m, 0, 1000000000))
|
나무를 자르는데 왜 이분탐색인가 싶었는데 어떻게 나무 높이가 1,000,000,000미터...
range의 중앙값을 일단 찔러보고 결과에 따라 위아래로 upper, lower bound를 좁혀가는 이분 탐색을 구현했다.
범위를 좁히다가 lower가 upper보다 큰 모순상황이 되면 upper( = 이전 재귀단계의 center)를 리턴
혹은 운좋게 찔러본 center 값이 맞으면 center를 리턴
나무 높이의 range는 10억인데 나무가 담긴 리스트 T의 길이는 1,000,000이다.
길이 1,000,000 리스트에서 max값 찾아 upper에 10억 대신 넣기 vs 그냥 10억부터 시작하기
리스트를 뒤져 max값을 뽑아도 그게 10억과 크게 차이나지 않으면 시간단축이 안될거라 판단해서
그냥 upper 시작값에 10억을 넣었다. 어차피 절반씩 금방 줄어들텐데.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
파이썬 백준 8983 사냥꾼 (0) | 2021.11.12 |
---|---|
파이썬 백준 2470 두 용액 (0) | 2021.11.11 |
파이썬 백준 1920 수 찾기 (0) | 2021.11.11 |
파이썬 백준 2503 숫자 야구 (0) | 2021.11.11 |
파이썬 백준 6603 로또 (0) | 2021.11.11 |