Search

BOJ 2805 나무 자르기

태그
이분 탐색
매개 변수 탐색
생성일
2024/12/11 12:11

문제 설명

•
적어도 MM미터의 나무를 얻을 수 있는 절단기 높이 HH의 최대값을 구하는 문제

예제 입력/출력

•
입력1
4 7 20 15 10 17
Plain Text
복사
•
출력1
15
Plain Text
복사
•
입력2
5 20 4 42 40 26 46
Plain Text
복사
•
출력2
36
Plain Text
복사

제약 조건

•
1≤N≤1,000,0001 ≤ N ≤ 1,000,000
•
1≤M≤2,000,000,0001 ≤ M ≤ 2,000,000,000
•
0≤0 ≤ 각 나무의 높이 ≤1,000,000,000≤ 1,000,000,000
•
H≥0H ≥ 0

문제 풀이

풀이1 브루트 포스 - O(109⋅N)O(10^9 \cdot N)
풀이2 파라매트릭 서치 - O(N⋅log2109)O(N \cdot log_{2}10^9)

문제 코드

•
풀이2 파라매트릭 서치 - O(N⋅log2109)O(N \cdot log_{2}10^9)
방법1
방법2