[JAVA] 2805 나무 자르기

 

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

2805번: 나무 자르기

---

클래스 2 달성 2일차 왜인지 모르겠지만 2가 달성이 돼있었다.

2++문제까지 모두풀어야 한다고 생각했는데 클래스 2 문제 필수문제만 풀면 인정을 해주는 모양이다.

그래서 2++ 문제까지 모두 푸는것으로 목표를 변경하기로 했다.

접근방식

1. 처음 문제를 풀고 읽고 이분탐색인지 눈치 채지못했다. 그래서 나무의 높이가 12 8 15 20 이렇게 4가지라면

톱날 높이가 12일때 자른다면 0 8 3 8 = 19 출력 이런 문제로 이해했다.

2. 2번째 테스트 케이스의 36을 보고 0부터 나무의키값의 가장 큰값의 범위 이분탐색이라고 생각했다. 

 

실수한부분

1. int형으로 합을 구해서 터질 가능성을 생각하지못했다. (체크해보지는 않음)

2. 잘린 나무크기의 합에 따라 left, right에 따라 늘려주고 줄여주는방식을 반대로 생각함 

 

import java.io.*;
import java.util.*;
public class boj2805 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(stz.nextToken());
		int M = Integer.parseInt(stz.nextToken());
		long sum=0;
		long comp[] = new long[N];
		stz = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++) {
			comp[i] = Integer.parseInt(stz.nextToken());
		}
		Arrays.sort(comp);
		long left=0,right=comp[N-1],mid=0;
		
		while(left<=right) {
			mid = (left+right)/2;
			sum = 0;
			for(int i=0;i<N;i++) {
				if(comp[i] > mid) sum += (comp[i] -mid);
			}
			
			if(sum >= M) {
				left = mid + 1;
			}else{
				right = mid - 1;
			}
		}
		System.out.println(right);
	}
}