[Java] 백준 2805번: 나무 자르기

[문제 바로 가기] - 나무 자르기

💡 접근 방식

매개 변수 탐색으로 풀이한 문제로 이분 탐색과는 다른 점이 있다.

이분 탐색은 값들 중에서 정렬된 배열에서만 사용 가능하며 target과 일치하는 값을 찾으면 함수를 종료하고 위치를 반환한다.

반면 매개 변수 탐색은 정렬이 되지 않아도 탐색이 가능하며, target과 일치하는 값을 찾아도 함수를 종료하지 않고 더 이상 탐색할 배열이 남아있지 않을 때까지 탐색을 계속한다. 이 문제처럼 조건을 만족하는 최댓값을 구할 때 쓸 수 있는 방법이다.

min의 초기값은 0, max의 초기값은 tree 배열에서 가장 큰 값으로 설정한 뒤 min과 max의 합의 절반인 mid를 선언해준다.

이때, M의 최댓값이 2,000,000,000이므로 sum은 long 타입으로 선언해주어야 한다.

tree 배열에서 mid를 뺀 값이 양수일때만 sum에 더한 뒤 이 값을 M과 비교해준다.

• 만약 M보다 크거나 같다면 -> min를 높여야 하므로 min = mid + 1
• M보다 작다면 -> max를 낮춰야 하므로 max = mid - 1

매개 변수 탐색 문제를 또 풀어봐야겠다!

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int tree[] = new int[N];
		st = new StringTokenizer(br.readLine());
		
		int min = 0;
		int max = 0;
		for (int i = 0; i < N; i++) {
			tree[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, tree[i]);
		}
		
		while (min <= max) {
			int mid = (min + max) / 2;
			long sum = 0;
			
			for (int treeHeight : tree) {
				if (treeHeight - mid > 0) sum += treeHeight - mid;
			}
			
			if (sum < M) max = mid - 1;
			else min = mid + 1;
		}
		
		System.out.println(max);
	}
}