[코테] 백준 2805번 : 나무 자르기 (java)

https://www.acmicpc.net/problem/2805

알고리즘 분류 : 이분 탐색, 매개 변수 탐색

 

❓문제

---

🔅해석

투포인터와 비슷하게 세개의 포인터로 문제를 푼다.

1 ~ 트리의 최대값까지의 배열을 만들어 start = 1, end = 트리의 최대값, mid = (start / end) / 2 로 초기화한다.

mid 값을 현재 절단기 높이라고 생각하고, 입력받은 트리의 순회하면서 mid 값을 각각 빼주고 sum에 더한다.

 

 

sum이 목표값보다 크다면 나무를 더 많이 잘랐다는 뜻으로 절단기 높이를 높이기 위해 start 값을 mid + 1로 설정한다.

반대의 경우, end = mid - 1로 설정한다.

 

다시 mid = (start + end) / 2로 설정해고 위와 같이 트리를 순회하면서 절단된 나무들의 합을 구한다.

이 때, sum == 목표값(M) 된다면, 반복문을 종료한다.

start <= end일 때  mid 값 계산을 하지 못하여 종료를 한다.

---

⭕정답 코드

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

public class Main {

	static int N, M;
	static int[] tree;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		tree = new int[N];
		int start = 0, end = 0, mid = 0;

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			tree[i] = num;
			end = Math.max(end, num);
		}

		int result = 0;
		while (start <= end) {
			mid = (start + end) / 2;

			long sum = 0;
			for (int i = 0; i < N; i++) {
				int cutLen = tree[i] - mid;
				sum += (cutLen <= 0 ? 0 : cutLen);
			}

			if (sum > M) {
				result = mid;
				start = mid + 1;
			} else if (sum == M) {
				result = mid;
				break;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(result);

		br.close();
	}
}

 

---

❗결과