문제
백준 2805번
https://www.acmicpc.net/problem/2805
목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
생각하기
이전에 Java로 풀었었던 문제이기 때문에 이분탐색의 개념은 이미 알고있던터라 쉽게풀었다.
이분탐색의 개념만 알고 있으면 쉽게 풀 수 있다.
이분탐색은 중앙값을 수정해가면서 탐색하며 원하는 값을 찾는 방법이다.
범위를 줄여가는 의미에서 전체 1씩 줄여가는 방향으로 완전탐색하고는 비교도 안될정도로 효율적인 방법이다.
이 문제도 binary_search를 사용하지 않고도 값을 찾을 수는 있겠지만, 테스트에서 통과는 할 수 없을 것이다. (너무나 비효율적이기 때문에 시간 초과가 나오게 됨)
또한 M값의 최대 범위가 2,000,000,000이기 때문에
long타입을 사용해야 함도 잊으면 안된다.
이전에 자바에서는 List를 만들어서 풀었지만 굳이 그렇게 풀 필요가 없다는 것을 알게 됬기 때문에 사용하지 않고 일반 array로 풀었다.
동작
// 기본적인 변수 생성
var N : Long = st.nextToken().toLong(); // 나무의 수 N
M = (st.nextToken()).toLong() // 나무의 길이 M
val trees = LongArray(N.toInt()); // 나무 길이가 담긴 배열
st = StringTokenizer(br.readLine())
for(i in 0 until N) {
trees[i.toInt()] = (st.nextToken()).toLong();
max_height = Math.max(max_height, trees[i.toInt()]);
}탐색을 하기전에 나무의 길이 값들을 담을 배열을 생성한다.
Long타입의 배열을 생성해야 한다.
while(max_height >= min_height) {
sum = 0;
trees.forEach {
// 나무의 길이가 절단기의 높이보다 크거나 같아야 자를 수 있음
if(it >= middle_height) {
sum += it - middle_height;
}
}
// 잘라진 나무길이의 합(sum)이 원하는 나무 길이(M) 보다 클 경우
// 높이를 높여야 함
if(sum >= M) {
min_height = middle_height + 1;
}
else {
max_height = middle_height - 1;
}
middle_height = (max_height + min_height) / 2;
}이분탐색을 하는 코드이다.
while문의 조건에 맞게 계속해서 순회를 하면서 잘라진 나무의 길이의 합인 sum이 M과 비교하여 어떤지 체크한다.
if(sum >= M)
만약 잘라진 나무들의 길이 합인sum이 M보다 클 경우
즉, 필요한 나무의 길이M 보다 절단한 나무의 길이가 더 길다 의미하므로 절단기의 높이를 수정해야 한다. -> middle_height 값을 높여야 함
(절단기의 높이는 middle_height임 중앙값을 기준으로 나무를 잘라서 길이를 비교함)
절단기의 높이(middle_height를 높일때는 중앙값을 최저 높이으로 해주고 최대 높이는 그대로 두면 된다.
예를 들어 가장 처음 나무를 자른다고 가정했을 때,
아래 사진처럼 나무를 처음에 중앙값으로 자른다
중앙 높이middle_height 의 높이로 자른다
그러면 max_height에서 middle_height 까지 나무가 잘리게 되는데
원하는 나무의 길이인 M이 잘라진 나무길이의 합 sum보다 더 길다면,
절단기의 높이를 높여야한다.
절단기의 높이는 곧 middle_height로, 우리가 중앙위치에서 자른다고 생각하면된다.
이제 중앙값인 절단위치를 높여야 잘라지는 나무의 길이가 짧아지므로 최저높이 min_height를 기존에 있던 middle_height로 수정하고 최대높이는 그대로 둔다.
여기서 최대한 효율적으로 하기위해서 기존에 있던 middle_height +1 한 값을 min_height로 수정한다.
이유는 어차피 방금 middle_height로 자른 위치는 정답이 아니기 때문에 포함시킬 필요가 없어서 범위에 넣지않기 위해서 + 1을 하는 것이다.
아래 사진처럼 범위를 계속 중앙 값을 기준으로 줄여나가면 된다.
반복은 당연히 while문을 사용해서 max_height 가 min_height보다 크거나 같을 때까지 반복하면된다.
코드
import java.util.*; import java.io.*; var max_height : Long = Long.MIN_VALUE /16; var min_height = 1L; var M = 0L; fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) var st = StringTokenizer(br.readLine()); var N : Long = st.nextToken().toLong(); // 나무의 수 N M = (st.nextToken()).toLong() // 나무의 길이 M val trees = LongArray(N.toInt()); // 나무 길이가 담긴 배열 st = StringTokenizer(br.readLine()) for(i in 0 until N) { trees[i.toInt()] = (st.nextToken()).toLong(); max_height = Math.max(max_height, trees[i.toInt()]); } binary_search(trees); } // End of main // 절단기로 설정할 수 있는 높이의 최대값 private fun binary_search(trees : LongArray) { var middle_height = 0L; var sum = 0L; while(max_height >= min_height) { sum = 0; trees.forEach { // 나무의 길이가 절단기의 높이보다 크거나 같아야 자를 수 있음 if(it >= middle_height) { sum += it - middle_height; } } // 잘라진 나무길이의 합(sum)이 원하는 나무 길이(M) 보다 클 경우 // 높이를 높여야 함 if(sum >= M) { min_height = middle_height + 1; } else { max_height = middle_height - 1; } middle_height = (max_height + min_height) / 2; } print(middle_height) } // End of binary_search
