백준 2805 나무 자르기 (JAVA 자바 풀이)
백준 2805 나무 자르기 (JAVA 자바 풀이)
문제
상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.
목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
💡 풀이 과정
Parametric Search 를 이용한 문제
먼저 정리하고 헷갈리지 않는 개념은 다음과 같다.
- 절단기 높이가 높아질 수록 가져갈 수 있는 양이 적어진다.
- 절단기 높이가 낮아질 수록 가져갈 수 있는 양이 많아진다.
5 21
4 42 40 25 46
케이스를 보면 어떻게 될까?
36으로 하면 20이 되므로 원하는 값보다 작아진다.
35로 하면 가져갈 수 있는 나무의 합이 23이 되므로 정답이 된다.
여기서 생각해볼 또 하나의 개념은 다음과 같다.
- 내가 가져갈 수 있는 나무의 합이 항상 일치하지는 않는다 -> 크거나 같을 수 있다.
어떤 높이 x에 대해서 생각해보면 가장 높은 높이부터 생각해보자.
제일 높은 높이는 0일 것이다.
거기서부터 절단기 높이를 낮추면 가져가는 양이 많아지고
어떤 높이 x를 찾았을 때 그때 최초로 가져갈 수 있는 양이 있는 높이 x가 정답이 될 것이다.
이때 모든 높이를 볼 수 없으므로 전체 탐색을 하면 시간초과를 받게 된다.
여기서 사용할 수 있는 것이 파라메트릭 서치이다.
x를 기준으로 어떤 determine 함수를 작성한다고 해보면 x 이하의 높이는 D(h)가 true, D(h) 는 false를 리턴하도록 한다.
왜냐하면 어떤 경계값 x를 기준으로 높아지면 내가 가져갈 수 있는 양이 적어지고 낮아지면 많아지기 때문이다.
public static boolean isPossible(int[] trees, int cutHeight, int thresholdHeight) {
long sum = 0;
for (int tree : trees) {
if (tree > cutHeight) {
sum += tree - cutHeight;
}
}
return sum >= thresholdHeight;
}
모든 나무에 대해서 내가 지정한 값과 비교를 하면서 절단하고 이를 sum 한다.
그 합이 내가 원하는 만큼보다 크거나 같으냐를 판단한다.
이 함수의 시간 복잡도는 모든 나무를 돌므로 O(n)이 된다.
- sum이 M보다 작다면, 저 잘라내야 한다 -> 그래야 더 많이 잘라낼 수 있으므로
- sum이 M보다 크거나 같으면 답의 후보가 된다. -> 답을 갱신하고 더 높은 M이 가능한지를 조사한다.
즉 true라면 점점 x의 범위를 높여 나간다.
조사해야 하는 값은 cutHeight가 되므로 원하는 조사 값의 최 하단을 0으로, 가장 높은 부분을 문제에서 주어진 최대값으로 설정하면 l =0, r = 1,000,000,000(1000000000)이다.
int l = minTreeHight;
int r = maxTreeHight;
int answer = -1;
while (l<=r){
int m = (l+r) /2 ;
if (isPossible(trees, m, treeLengthInNeed)){
answer = m;
l = m +1;
} else{
r = m-1;
}
}
중앙 값에 대해서 판정 함수를 반복하면서, 내가 원하는 값을 가져갈 수 있다면 -> 답이 된다.
동시에 answer는 갱신되고, 문제는 더 높은 범위도 답이 될 수 있으므로 l을 올려서 범위를 좁혀준다.
없다면 절단기는 낮아져야 하므로 r은 올라가도록 한다.
문제에서 무조건 가져갈 수 있다고 하였으므로 answer는 무조건 한번 갱신이 될 것이다. 따라서 아무 값이나 초기값으로 해도 된다.
전체 시간 복잡도를 살펴보자.
10억 범위에 대해서 log2H만큼 탐색을 한다. (이분 탐색 log2n)
이때 isPossible 함수의 시간 복잡도는 O(N)이므로
-> O(N * logH)
백만 x 30 -> 3천만 정도의 연산이 예상된다.
💡 코드 구현
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int treeCounts = Integer.parseInt(stringTokenizer.nextToken());
int treeLengthInNeed = Integer.parseInt(stringTokenizer.nextToken());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int[] trees = new int[treeCounts];
while(treeCounts-->0){
trees[treeCounts] = Integer.parseInt(stringTokenizer.nextToken());
}
// 1. 절단기 높이의 탐색 범위를 정한다.
// 2. 임의의 절단기 높이에 대해
// 2-1. 원하는 만큼 나무를 가져갈 수 있다면 높이를 높인다.
// 2-2. 원하는 만큼 가져갈 수 없다면 높이를 낮춘다.
// 3. 원하는 만큼 가져갈 수 있던 높이 최대값을 출력한다.
int l = 0;
int r = 1000000000;
int answer = -1;
while (l <= r) {
int x = (l + r) / 2;
if (isPossible(trees, x, treeLengthInNeed)) {
answer = x;
l = x + 1;
} else {
r = x - 1;
}
}
System.out.println(answer);
}
public static boolean isPossible(int[] trees, int cutHeight, int thresholdHeight) {
long sum = 0;
for (int tree : trees) {
if (tree > cutHeight) {
sum += tree - cutHeight;
}
}
return sum >= thresholdHeight;
}
}
참고자료: 패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java