https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따
www.acmicpc.net
해결 방법
> 이분 탐색을 이용한다.
이분 탐색
- 탐색기법중에 탐색 범위를 반으로 나누어 탐색함에 따라 시간이 절약되는 탐색기법이다.
> left, right(최소, 최대값)을 설정한다.
> mid = (left + right)/2를 설정한다.
> mid와 target을 비교한다.
> mid < target 이면 left = mid + 1로 설정한다.
> mid > target 이면 right = mid - 1로 설정한다.
> mid == target 이면 반복문을 탈출한다.
> left > right가 될 때 까지 위의 과정을 반복한다.
후기
> python3로 제출하니까 시간초과가 떴다.
> pypy3로 제출하라는 조언을 듣고 pypy3로 제출하니 통과되었다.
참고 자료
> What is pypy
https://pypy.org/performance.html
Performance
Contents Profiling: vmprof Optimization strategy Micro-tuning tips This document collects strategies, tactics and tricks for making your code run faster under PyPy. Many of these are also useful h
www.pypy.org
> python vs pypy
python 을 더욱 힘세고 강하게! PyPy (pypy)
Python 은 엄청난 생산성을 가진다. 오죽하면 언어의 모토가 "Life is Short, You need Python." 이겠...
blog.naver.com
> 정확하진 않지만 객체 메소드 호출에 있어서는 python이 더 빠를수도 있다.
https://www.acmicpc.net/board/view/32552
글 읽기 - 제코드가 pypy3 보다 python3에서 훨씬 빠른 이유가 뭔가요?
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
tall = list(map(int, input().split()))
left, right = 0, max(tall)
while left <= right:
mid = (left + right) //2
total = 0
for i in tall:
if i >= mid:
total = total + (i - mid)
if total > m:
left = mid + 1
elif total < m:
right = mid - 1
else:
print(mid)
sys.exit()
print(right)
'알고리즘' 카테고리의 다른 글
| 백준_15997_승부 예측 (0) | 2020.02.17 |
|---|---|
| 백준_10815_숫자 카드(이분 탐색) (0) | 2020.02.16 |
| 백준_15957_음악추천(해결 못함) (0) | 2020.02.14 |
| 백준_2385_Secret Sharing(해결 못함) (0) | 2020.02.13 |
| 백준_9203_호텔 예약(해결 못함) (0) | 2020.02.12 |
댓글