1. 문제 링크
2. 문제 및 입출력예제
3. 문제 풀이
나무 높이 범위가 매우 커서 이분탐색으로 풀었다.
최댓값과 자른 값의 중간 값을 이용해 중간값보다 큰 나무에서 그만큼 베어간다.
자른 나무의 합이 원하는 값인 M보다 작으면 높이를 낮춰야 하니까 현재 최댓값을 중간값으로 넣고 반복한다.
만약 자른 나무의 합이 M보다 크거나 같아지면 중간값보다 하나 큰 값을 넣고 반복한다.
뭔가 하나씩 풀어쓰려니까 애매한데
자른 값이 모자라면 자르는 높이를 낮추고, 자른 값이 넘치면 자르는 높이를 높이면서 값을 찾는다.
4. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
String[] nm = br.readLine().split(" ");
int N = Integer.parseInt(nm[0]);
int M = Integer.parseInt(nm[1]);
int use = 0;
int max = 0;
int[] tree = new int[N];
String[] split = br.readLine().split(" ");
for(int i=0;i<N;i++) {
tree[i] = Integer.parseInt(split[i]);
max = Math.max(max, tree[i]);
}
while(use < max) {
int mid = (use + max) /2;
long sum = 0;
for(int h: tree) {
if(h-mid>0) {
sum+=h-mid;
}
}
if(sum < M) {
max = mid;
}
else {
use = mid + 1;
}
}
System.out.println(use-1);
}
}
'ALGORITHM' 카테고리의 다른 글
백준 27160 할리갈리 (Java) (0) | 2023.03.26 |
---|---|
백준 1717 집합의 표현 (Java) (0) | 2023.03.25 |
백준 17144 미세먼지 안녕! (Java) (0) | 2023.03.23 |
백준 15683 감시 (Java) (0) | 2023.03.22 |
백준 1018 체스판 다시 칠하기 (Java) (0) | 2023.03.21 |