[백준] No.2805 - 나무 자르기 (C++)

문제

https://www.acmicpc.net/problem/2805

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과 필요한 나무의 길이가 일치한다는 보장은 할 수 없으므로 

크거나 같은 경우는 아래의 코드처럼 같이 처리해주어야 한다.

 

if(cut_sum < need_len){
  right = mid -1;
}else{
  left = mid +1;
  if(answer < mid)
    answer = mid; 
}

 

추가적으로 해당 문제의 cut_sum은 int형의 범위를 초과할 수 있으므로 long long으로 선언해주자.

 

본인은 left의 시작 값을 0이 아닌 가장 작은 나무의 길이로 선언하여 틀렸다...

다음 parametric search문제로는 백준 - 숫자구슬(2613)을 추천한다.

 

코드