상근이는 나무 M미터가 필요하다. 절단기에 높이 H를 지정해서 H미터 이상의 나무들을 잘라서 필요한 나무를 가져가려고 한다.
M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
풀이
이전 이코테 책에서 파이썬으로 풀었던 경험이 있어서 바로 이진탐색으로 접근하였다. 이전에 포스팅한 적 없으니 가볍게 풀이 설명은 해야겠다.
우리가 구하려는 것은 절단기의 높이 H.
나무들의 높이가 20 15 10 17 일 때, H를 0으로 하면 가져가는 나무 양이 많아지고, 나무들 중 가장 높은 나무의 높이를 H로 설정하면 가져가는 나무 양이 적어진다. 그렇기 때문에 두 값 사이에서 적절한 값을 찾아나가야 한다.
그렇다면 어떻게 찾을 것인가. 바보같이 0부터 20까지 순차 탐색을 진행하게 되면 나무의 최대 길이 M(2,000,000,000)까지 찾는 경우가 생길 수도 있다. 시간복잡도 O(N)의 N이 20억이므로 1초당 1억번의 연산을 한다고 하면 tle(time limit error)가 발생한다. 그렇기 때문에 시간 복잡도를 줄이기 위한 방안을 생각해야하고, 이에 적용할 수 있는 기법이 이진 탐색(Binary Search)이다. 이진 탐색은 O(logN)의 시간 복잡도를 가진다.
M이 20억(2^30)이므로 O(logN)의 시간복잡도를 갖는 기법으로 풀면 적당하다.
이진 탐색을 사용한다고 했고, 적합한 높이는 어떻게 찾아갈까?
- start 0과 end (나무들 중 최대값)을 합쳐서 반으로 나눈 mid 를 하나 설정한다.
- mid 보다 큰 나무들을 자른 값을 합하여 sum 에 저장한다.
- sum 에 저장한 값이 우리가 필요한 M 보다 크면 우리는 최대 높이 H를 찾을 것이기 때문에 start = mid+1 로, end 는 그대로 가져가서 다시 이진 탐색을 실행한다.
- M 보다 작으면 H의 길이가 더 작아져야 하기 때문에 start는 그대로 end = mid -1로 한다.
- 3, 4를 반복하면서 알맞은 h 값을 찾아간다.
!! 아 매우 중요한 것을 놓쳤네. 이진탐색을 하기 위해서는 탐색하려는 자료를 정렬하는 것이 매우 중요하다. 이 문제 같은 경우는 배열 속에서 값을 찾는 게 아니기 때문에 그럴 필요는 없지만! 이외의 배열 속에서 이진 탐색을 해야하는 경우가 생기면 정렬을 하고 이진 탐색하는 것을 잊지말자!!
알고리즘은 이렇게 해결하였고, 아래는 자바로 풀면서 놓쳤거나 부족했던 풀이 방법이다.
- sum 값을 int로 설정하였었다. 백준에서 2% 이상으로 못올라가고 계속 실패하길래 이것 저것 고치다가 sum을 long 자료형으로 수정해주었다.
아마 나무의 길이가 19억, 20억이고 자르려는 높이 mid가 1이라고 가정하면 sum은 int의 자료형 범위를 초과하게 되어서 연산이 되지 않는 것 같다. 앞으로도 자바로 해결하면서 주의해야할 점인 것 같다.
- 내 풀이는 재귀형식으로 풀었는데, 이전 파이썬 풀이는 while문으로 해결하기도 했고, sds 강사님 답안도 while 반복문으로 해결하셨다. 재귀로 풀려고 생각하기 전에 반복문으로 풀려는 시도를 하도록 노력해야겠다. 재귀로 풀게되면 메모리 초과가 발생할 수도 있기 때문에
자바 코드와 파이썬 코드를 순이다.
java
package Day2_TimeComplexity;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj2805 {
static int n, res; // 사용자 입력, 결과
static long m; //
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = Integer.parseInt(stk.nextToken());
m = Integer.parseInt(stk.nextToken());
res = -1;
arr = new int[n];
stk = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(stk.nextToken());
}
Arrays.sort(arr);
int start = 0;
int end = arr[n - 1];
binarySearch(start, 1000000000);
System.out.println(res);
}
static void binarySearch(int s, int e) {
long sum = 0;
if (s > e) {
return;
}
int mid = (s + e) / 2;
for (int i = 0; i < n; i++) {
if (arr[i] > mid)
sum += arr[i] - mid;
}
if (sum >= m) {
if (mid > res)
res = mid;
binarySearch(mid + 1, e);
}
else {
binarySearch(s, mid - 1);
}
}
}python
n, m = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()
start = 0
end = max(trees)
resul = 0
while(start<= end):
total = 0
mid = (start+end)//2
for x in trees:
if x > mid:
total += x - mid
if total < m:
end = mid -1
else:
result = mid
start = mid + 1
print(result)