Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/2805
풀이
solved.ac 난이도: Silver 3
이분 탐색의 응용인 parametric search를 이용하는 대표적인 문제이다.
이분 탐색(binary search)과 parametric search의 차이점은 라몽님의 게시글을 참조하자.
이진탐색(Binary Search)와 Parametric Search - 라몽의 배움일기
left는 0에서부터 right는 가장 긴 나무의 길이에서부터 시작한다.
mid( = (left +right) /2 )를 나무를 자르는 높이라고 하면 잘린 나무들의 길이 cut_sum을 구할 수 있다.
1. cut_sum이 필요한 나무보다 작을 때
mid값을 더 낮춰야 잘린 나무들의 길이가 커진다.
따라서 right = mid -1로 설정해준다.
2. cut_sum이 필요한 나무보다 크거나 같을 때
만약 cut_sum이 크다면 mid 더 높여서 가장 긴 높이를 구해야 한다.
따라서 left = mid +1로 설정해준다.
만약 cut_sum이 정확히 필요한 나무길이와 일치한다면 동일하게 left = mid +1을 진행할 경우
cut_sum이 항상 작게 되어 1번 경우가 지속적으로 선택될 것이다.
따라서 answer변수를 선언하여 answer < mid인 경우 해당 mid를 answer로 저장해 두자.
크거나 같은 경우를 함께 구현하는 이유는
4 4
20 15 10 17
와 같은 경우를 처리하기 위해서이다.
4 이상의 길이를 얻을 수 있는 최대 높이는 16이다.
하지만 (20-16) + (17-16) = 5로 필요한 길이 4와 같지는 않다.
17일 때는 (20-17) = 3으로 4보단 부족하다.
즉, 정확히 cut_sum과 필요한 나무의 길이가 일치한다는 보장은 할 수 없으므로
크거나 같은 경우는 아래의 코드처럼 같이 처리해주어야 한다.
1
2
3
4
5
6
7
|
if(cut_sum < need_len){
right = mid -1;
}else{
left = mid +1;
if(answer < mid)
answer = mid;
}
|
cs |
추가적으로 해당 문제의 cut_sum은 int형의 범위를 초과할 수 있으므로 long long으로 선언해주자.
본인은 left의 시작 값을 0이 아닌 가장 작은 나무의 길이로 선언하여 틀렸다...
다음 parametric search문제로는 백준 - 숫자구슬(2613)을 추천한다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] No.1062 - 가르침 (C++, 비트마스크) (0) | 2021.01.16 |
---|---|
[백준] No.14889 - 스타트와 링크 (C++, 비트마스크) (0) | 2021.01.15 |
[백준] No.2613 - 숫자구슬 (C++, parametric search) (0) | 2021.01.09 |
[백준] No.10165 - 버스 노선 (C++) (0) | 2021.01.07 |
[백준] No.2513 - 통학버스 (C++) (0) | 2021.01.04 |