[BAEKJOON] 2805번 : 나무자르기

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());
		
		long[] treeArr = new long[N];
		
		st = new StringTokenizer(br.readLine());
		
		// 목재절단기의 최소 높이
		long min = 0;
		
		// 목재절단기의 최대 높이
		long max = 0;
		
		// 나무들 세팅
		for(int i=0;i<N;i++) {
			treeArr[i]=Long.parseLong(st.nextToken());
			if(max < treeArr[i]) {
				max = treeArr[i];
			}
		}
		
		br.close();
		
		// 최소 높이가 최대 길이보다 커질 때까지 반복
		while(min<=max) {
			long mid = (min+max) / 2;
			
			long rest = 0;
			for(int i=0; i<N; i++) {
				if(treeArr[i] > mid) {
					rest += (treeArr[i] - mid);
				}
			}
			
			// 잘리고 남은 나무의 길이가 M보다 많거나 같을 때, 목재절단기의 최소 높이를 높인다.
			if(rest>=M) {
				min = mid + 1;
			}
			// 잘리고 남은 나무의 길이가 M보다 적을 때, 목재절단기의 최대 높이를 줄인다
			else {
				max = mid - 1;
			}
		}
		
		// 최대 높이 출력
		System.out.println(max);
		
	}
}

 

이번 문제의 중요한 부분은 아래와 같습니다.

 

1. 최소 높이, 최대 높이, 계산에 필요한 변수를 long으로 선언 → min과 max를 연산한 결과가 int의 범위를 벗어날 수 있음.

2. 절단기의 최소 높이는 0 이상. 

3. 1654번 랜선자르기와 비슷한 유형의 문제

 

소스 설명은 주석을 참고해주세요.

 

좋은 지적과 지식 공유는 언제나 환영합니다^^