2805번: 나무 자르기
문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고,
www.acmicpc.net
<내 코드>
def binarySearch(M, tree):
start = 1
end = max(tree)
while start <= end:
leng = 0
mid = (start + end) // 2
for i in tree:
if i >= mid:
leng += i - mid
if leng >= M:
start = mid + 1
else:
end = mid - 1
return end
N, M = map(int, input().split())
tree = list(map(int, input().split()))
sortTree = sorted(tree)
print(binarySearch(M, sortTree))이분 탐색 알고리즘을 이용해서 푸는 문제다. 알고리즘만 알고 있으면 생각보다 간단한 문제였다. 같은 코드로 채점 했는데 pypy3는 588ms가 걸리고 python3는 2984ms 가 걸리면서 다소 큰 차이가 있었다.
반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
| [백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍) (0) | 2020.08.24 |
|---|---|
| [백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍) (0) | 2020.08.23 |
| [백준 1920] 수 찾기 - Python (이분탐색) (0) | 2020.08.18 |
| [백준 11866] 요세푸스 순열 - Python (0) | 2020.08.18 |
| [백준 1966] 프린터 큐 - Python (0) | 2020.08.17 |