[Binary Search] 백준 - 2805

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

2805번: 나무 자르기

 

우선 해당 문제는 이분 탐색의 종류중에서, 약간 응용 버전인, Parameter Search이다.

어떤 배열의 값들은 알수없으나, 정렬이 되어있는 경우 사용할수 있고, 특정 조건들을 만족하는 답중에서, 최대 or 최소를 구할때 사용한다.

 

아래와 같은 구조로 해당 문제의 기준을 세웠다.

1. 정답 범위, int 자료형은 2억까지이므로, 20억의 연산과정값이 발생할수있어, 연산과정은 long으로 사용했다.

2. 최대 자르는 길이는 나무의 길이의 최대값이다. 즉 1~ 나무 최대값까지 배열이 탐색 범위이다.

3. 우선 이분탐색은 사전 조건이 정렬이 되어있어야 하므로, 정렬을 하고, 마지막 값을 2번으로 대입해준다.

4. 최대값이므로, 각각의 항목을 구해서 합을 return해주는 함수를 구현, 해당 함수로값을 판별해서 answer을 구한다.

answer은 값이 생길때마다 계속 update 되기때문에 해당 마지막 update가 최대값으로 보면된다.

 

아래는 소스이다.