본문 바로가기

ALGORITHM

백준 2805 나무 자르기 (Java)

1. 문제 링크

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

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