백준 2805: 나무 자르기 (Swift)

전형적인 이분탐색(Binary Search)에서 조금의 응용만 한다면 풀 수 있는 문제이다.

블로그들을 찾아보면 많은 알고리즘이 그렇듯 이분탐색에서 start, end 인덱스를 사용하는 방식이 천차만별인 것 같다.

나는 start와 end를 "아직 후보군에서 탈락하지 않은 것들"의 양 끝을 가리키도록 한다.

따라서 start가 end보다 "커지면"!! ( 같을 때까지는 아직 그 마지막 원소를 탐색해야 하므로.. ) 탐색을 종료하고 None혹은 Never를 return한다.

 

여기서는 나무를 최소 m만큼 가져갈 수 있게 잘라야하므로, 딱 m을 가져가지 못할 수 있다.

 

예를 들면, 3만큼의 길이를 가져가야하는데, 길이가 10인 나무만 두 그루 있는 경우, 우리는 4 만큼의 길이를 가져갈 수 밖에 없다.

 

따라서 가져갈 수 있는 나무의 길이가 목표 길이인 m보다 길 경우 last라는 변수에 저장해놓는다 ( 혹시 지금의 길이가 m 이상의 길이로 가져갈 수 있는 최선의 높이일 수 있으므로)

 

그렇다면 지금 가져갈 수 있는 나무의 길가 target과 같다면 바로 return해줘도 되는 것일까?

혹시나 나무를 절단하는 높이가 조금 달라도 같은 길이만큼의 나무를 가져가야하는 경우는 없을까?

즉, 우리는 m의 길이를 가져갈 수 있는 여러 "절단 높이" 중 가장 작은 값을 찾아야하는 것은 아닐까?

 

결론은 아니다.

나무 배치가 어떻게 되어있든, 높이를 1이라도 낮추면 어느 쪽에서든 하나는 가져갈 나무의 길이가 더 많아질 수 밖에 없고,

높이를 올렸을 때, 어떤 나무에서든 가져갈 수 있는 길이가 하나라도 줄어들 수 밖에 없다.

 

*(22.08.17 추가작성)

아래의 func tree(){}함수는 전체 코드 8~16번에 있는 get_tree()함수와 같은 함수인데, 고차함수를 사용해서 간결하게 작성해본 경우이다!

필자는 나만의 알고리즘 Note를 만들어놓고, 코테 시즌에는 이를 모두 외워 틀에 맞추어 문제를 풀이한다.

코테 시즌이 아닐 때( 오늘과 같이 ) 풀면 아래처럼 틀에 박히지 않은, 좀 더 효율적인 코드에 대해 생각해볼 수 있는 것 같다