[백준 2805] 나무 자르기_자바Java

1. 문제

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

2. 느낀점

문제를 풀면서 간과했던 부분은 잘라진 나무 길이의 합을 구할 때 나무길이 - mid 연산이 수행되는데, 이때 음수가 발생하는 경우는 합에 계산되지 않도록 처리해야 하는 점이었다. 예제로 주어진 수들이 큰 수가 아니었어서 하나하나 계산 해보고, 코드는 디버깅을 통해 비교하자 바로 문제점을 찾을 수 있었다.

+) N, M의 범위가 int 범위를 넘지 않기 때문에 left, right 범위도 그 안에 속할 것이고 따라서 N, M, left, right 모두 int 타입으로 선언했다. 그러나, 잘라진 나무 길이의 합은 그 범위를 초과할 수 있으므로 long 타입으로 선언했다. ( ᐛ )و

3. 코드

• Memory: 167,832KB
• Time: 484ms

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 in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int trees[] = new int[N];
	
		// 나무길이 입력받기 + right 값은 나무 최대 길이 찾아 저장
		int left = 0, right = Integer.MIN_VALUE;
		st = new StringTokenizer(in.readLine(), " ");
		for(int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			trees[i] = num;
			right = Math.max(right, num);
		}
	
		while(left <= right) {
			int mid = (left + right) / 2;
			long sum = 0;
			
			// 잘라진 나무 길이의 합
			for(int i = 0; i < N; i++) {
				// 이 조건을 넣지 않으면 음수값이 더해지기 때문에 제대로 된 계산이 되지 않음
				if(trees[i] > mid) sum += trees[i] - mid; 
			}
			
			if(M <= sum) left = mid + 1;
			else right = mid - 1;
		}
		
		System.out.println(right);		
		in.close();

	}
}