BOJ 1114번 통나무 자르기

1114번: 통나무 자르기

 

백준 1114번 통나무 자르기 문제는 이분 탐색에 미숙하던 과거의 나에게 충격을 줬던 문제다. 과거 이분 탐색을 사용할 때 에는 정해진 크기의 배열 (또는 벡터 등)이 있을 때, 저장된 데이터에 대하여만 이분 탐색을 수행했었다.

 

하지만 이런 유형의 문제를 풀고 난 뒤, 하나의 고정관념이 사라졌다. 저장되있지 않은 대상에게도 이분 탐색을 적용할 수 있다는 깨달음을 얻은 것이다.

 

우선 문제 자체는 이분 탐색을 이용하면 간단한 문제이므로 이분탐색 알고리즘 자체에 대하여 모른다면 아래의 더보기 포스팅을 참고하자.

알고리즘 : 이진 탐색 (=이분 탐색, binary search)

 

---

우선 문제 해석을 해보자.

 

길이가 주어진 긴 통나무가 주어지고, 그 통나무에 자를 수 있는 위치가 주어진다. 즉 내가 자르고 싶은 곳을 마음대로 자를 수는 없고, 정해진 포인트를 자를지 여부는 선택할 수 있는 상황이다.

자를 수 있는 횟수가 주어지기 때문에 (해당 횟수 미만으로 자르는 것은 상관없다.) 모든 포인트를 다 자를 수 있을 수도 있고 없을 수도 있다.

이러한 조건에서 통나무를 주어진 횟수 이하의 절단을 한다. (그러면 절단한 횟수 +1 개의 통나무 조각이 나올 것이다.)
절단을 한 뒤, 생성된 조각의 길이중 가장 긴 통나무가 있을 것이다. 그 가장 긴 통나무의 길이를 가장 짧게 절단한다면 그 길이는 몇인가? 또한 어디부터 자르기 시작해야 하는가?

 

처음 이 문제를 해결하려 할 때, DP와 그리디를 이용할 생각을 했었다. 임의의 포인트에서 시작했다면, 그 포인트에서 시작한 최적해를 그리디 하게 구하려 했다. 이때 남은 커팅 횟수와 남은 길이를 이용해 DP 테이블을 구성하여 속도를 높이는 것이다.

 

하지만 이 방법으로는 시간 초과의 늪에서 벗어날 수 없었다.

---

그래서 해법은?

 

해법 자체는 간단했다. 최초 길이 n1을 가정하고, 모든 조각을 그 길이 이하로 자를 수 있는지만 체크한다.

만약 n1으로 자를 수 있다면 0~n1의 범위의 중간값을 n2로 하여 시도해본다, 자를 수 없다면 n1 ~ 전체 길이 범위의 중간값으로 시도해본다.

 

이렇게 n1, n2, n3.... 을 탐색해 나간다. 그러다 만약 n10에서는 잘렸는데, n10 + 1의 길이에서는 안 잘린다면? 답은 n10이 되는 것이다.

 

이 방법을 이용하면 주어진 통나무의 최대길이 1,000,000,000를 이분 탐색하는 것이 되기 때문에 시간 복잡도는 O(C * logL) 이 되어 시간 합격을 받을 수 있다. (당연히 자를 수 있는지 판단은 그리디 테크닉을 넣어야 불필요한 연산이 줄어든다.)

 

위에서도 한번 언급했지만, 이 해법을 떠올리고 충격을 받았다. n1, n2, n3... 은 직접 저장한 값이 아닌 정수 영역의 임의의 값이 되기 때문이다.

 

지금도 이럴 때마다 알고리즘 문제 푸는 것이 참 재미있다.

---

DP + 그리디 방법 (최초 시도 방법) 은 왜 시간 초과가 났을까?

 

범위가 조금 더 작았다면 아마 solve 판정을 받을 수는 있었을 것이다.

하지만 지금처럼 매우 큰 범위에, 많은 포인트를 자를 수 있는 상황이라면 (예를 들어 1m마다 자를 수 있다면) 그리디 에서의 임계치를 설정하기가 힘들다. 1억 m에서 1m 단위로 자를 수 있는데 정확히 1m 마다 모두 자를 수 있다면 그나마 낫지만, 1m, 2m, 3m....로 점진적으로 잘라 나가야 하는 형태이거나, 중간에 포인트 간 거리가 길어질 경우, 마지막에 가서 자를 수 있는 횟수가 모자란 경우 등에 상황에서 분명 O(n^2) 이상의 연산이 일어난다.

 

그에 비하면 이분 탐색을 이용한 방법은 최악의 상황인 (L : 1,000,000,000 /  K, C : 10,000)의 상황에서도 10,000 * 40의 연산 횟수로 끝난다.

---

 

code :

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지