[백준 / BOJ] 1114 통나무 자르기

문제

출처 : https://www.acmicpc.net/problem/1114

1114번: 통나무 자르기

길이 L인 통나무가 주어지고, 이 통나무를 자를수있는 위치가 K개 주어진다.

(통나무는 입력된 위치에서만 자를수 있다.)

통나무를 자를수있는 횟수 C가 주어졌을때, 통나무를 적절히 잘라 통나무의 가장 작은 길이가 최대가 되며, 이때 가장 먼저 잘라야하는 인덱스를 구하는 프로그램을 만드는 문제다. 

 

풀이

결정문제 패턴으로 자주 나오는 문제다.

 

자를수있는 위치가 최대 10,000이므로 모든 경우를 구할려하면 시간초과가 난다.

이 문제를 결정문제로 변경해서 풀면 쉽게 풀수있는데,

 

문제가 요구하는 바를 결정문제 패턴으로 바꾸고 해당 물음에 답하는 알고리즘을 만들자.

 

기존 문제의 요구 : "길이가 L인 통나무의 적절한 위치를 선택해 C번 잘라 각각 통나무의 최대길이가 최소가 되게하자."

->

결정문제 패턴 : "길이가 L인 통나무를 C번잘랐을때, 나온 통나무들의 길이를 length이하가 되게할수있는가?"

 

통나무의 최대길이는 1 <= L <= 1,000,000,000 이므로, 길이를 +1씩 늘려가는 방법으로는 풀수없다.

따라서, 이분탐색을 통해 length를 설정해준다. 

통나무의 최소길이 = 1, 통나무의 최대길이 = L 

length = (통나무의 최소길이 + 통나무의 최대길이) / 2;

 

1,000,000,000의 경우 2^30보다 작으므로, 30번 반복해주면 항상 답을 구할수있기때문에, while(l<=r)식으로 반복하지않고, for(int i = 1; i <= 30...)처럼 반복시켰다.

이런 형태의 반복은, 30번 탐색하면, 1/(2^30)만큼 오차범위가 줄어들기때문에, 삼분탐색이 아닌 이분탐색에서는 항상 정답을 보장한다. 또한, L의 길이에 상관없이 반복횟수가 일정하므로 프로그램의 수행시간을 예측하기 쉽다.

(물론, 이분탐색 구현하듯이 l <= r 처럼 반복해줘도 상관없기는 하다. )

 

이제 통나무의 길이를 length이하로 자르는 방법이 존재하는지 구하면된다.

(자르는 지점을 idx라고 하겠다.)

우선, 불변의 법칙은 현재 idx까지의 통나무 길이가 length이하일 경우 자르지 않아줘도 된다. (결국 우리는 모든 통나무의 길이를 각각 length이하로 만들수있는지만 확인하면 되기 때문에..) 즉, length범위를 벗어날때까지 통나무를 자르지않다가, 자르는범위가 length보다 커질경우, 이전 위치에서 통나무를 잘라주면된다.

 

이때, 첫번째로 자르는 위치를 정해주기위해, 뒤에서 부터 탐색해준다. (이걸 구현하는게 까다로웠다..)

 

구현중 예외처리할것이 있었는데,

 

1. 각 통나무의 자르는지점을 모두 자르더라도 통나무의 길이를 length 이하로 만들수없을때

-> 자르는 지점1, 자르는지점 2의 길이가 length보다 길다면 절대로 length이하로 만들수없다.

 

2. 각 통나무를 적절히 잘라 길이를 length이하로 만들었지만, 자를수있는 경우가 더 남아있을때

이 경우, 항상 첫번째 자르는지점을 잘라준다. (최소위치를 출력해야하기때문)

 

풀면서 여러번 틀렸는데, 다음은 틀려가며 만든 반례다.

 

1000000000 10 10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

 

출력 : 900000000 1

 

9 4 2
2 4 5 7

 

출력 : 4 2

 

100 10 2
1 10 20 30 40 50 60 70 80 90

 

출력 : 20 1

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1114%20%ED%86%B5%EB%82%98%EB%AC%B4%20%EC%9E%90%EB%A5%B4%EA%B8%B0/main.cpp

devxb/JJUNalgo