[백준/2805] 나무 자르기 ( 자바 )

 

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

 

이 문제는 이진트리를 이용한 최댓값을 구하는 문제이다.

정해진 범위 내에서 최대한의 높이를 잘라서 원하는 길이 M을 얻어야 한다.

 

1. 익숙한 유형이었는데 실수했던 부분은, min 값을 나무길이의 최소값으로 잡았다.

M의 길이는 1부터 20억까지라고 되어 있다. 즉, min값은 나무길이 중 최솟값보다 더 작은 1도 될 수 있다.

정해진 공식에 따라서 문제를 푸는 습관이 었어서 그런지 아무 의심없이 풀은 결과 틀렸다.

따라서 변수설정도 문제에 따라서 달라질 수 있음을 잘 생각하고 풀어야한다.

 

2. 또한 언제 berak를 걸어서 나와야하는지 고민이 있었다. 내 코드는 무한루프가 돌고 있었다.

mid값을 초기에 설정하고 while문 앞에서는 min과 max값을 움직이면서 mid를 조정했다.

하지만 올바른 문제풀이는,,, min값과 max값을 적절히 변형하고 while 문 안에 다시 계산이 돌아올때마다

mid 값을 설정해 주어야 한다. 말이 어려워 보이는데,,, 즉 내가 신경써야 하는 부분은 min과 max의 값을 서서히 올바른 방향으로 줄여나가는 것이다. 그래서 정답도 max값을 출력해야 한다. 

 

왜냐하면 계속 +1, -1형식으로 값을 줄여나가므로 내가 원하는 최댓값을 max에 있을 것이기 때문이다.

 

package bj;

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long M = sc.nextInt();

		int[] array = new int[N];
		for (int i = 0; i < N; i++)
			array[i] = sc.nextInt();

		Arrays.sort(array);
		long min = 1;
		long max = array[N - 1];
		long mid = 0;
		long val = 0;

		while (min <= max) {
			mid = ( min + max ) / 2;
			val = 0;
			for (int i = 0; i < N; i++) {
				if(array[i]-mid<=0) continue;
				val += array[i]-mid;
			}
			
			// 오 더 높일 수 있네?
			if (val >= M) {
				min = mid+1;

			// 좀 낮춰야대
			} else {
				max = mid-1;
			}
		}

		System.out.println(max);
	}

}