[백준] 2805번 나무 자르기(JAVA)

문제

- 상근이는 절단기에 높이 H를 지정

- 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라감

- 한 줄에 연속해있는 나무를 모두 절단

- 높이가 H보다 큰 나무는 H 위의 부분이 잘림

- 상근이는 나무를 필요한 만큼만 집으로 가져감

- 나무는 M미터가 필요함

 

고찰

문제를 빠르게 이해하고 코드를 이분 탐색으로 짜는 데에는 시간이 얼마 안걸렸었다. 하지만, 이상한 곳에서 생각을 잘못하고 있었어서 계속해서 틀렸습니다.를 본 문제다. 테스트 케이스도 맞고 인터넷에서 찾은 다른 테케들도 다 맞는데 계속 틀렸다고 나와서 너무 화가 났었는데 정말 어이없는 곳에서 틀렸었다. 매번 자료형 때문에 틀리면 다음에는 자료형 때문에 틀리진 않을 거야!!!!! 하지만.... 이번에도 자료형에서 틀렸다. long으로 해줘야 하는 걸 int로 하여 문제가 있었다..... 진짜 다음엔.... 자료형 때문에 틀리는 일은 없도록......

 

코드

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        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());		// 필요한 나무의 길이

        int[] tree = new int[N];				// 나무들의 길이 저장 배열

        int max = Integer.MIN_VALUE;				// 이분 탐색을 위한 변수
        int min = 0;						// 이분 탐색을 위한 변수

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

        long result = 0;				// 이 값 때문에 틀렸습니다를 몇번을 본건지....
        while(min <= max){
            int mid = (min + max) / 2;			// 중앙값 계산
            result = 0;
            for(int i = 0; i<N; i++){
                if(tree[i] > mid){			// 중앙값보다 큰 애들만 잘라주기
                    result += (tree[i] - mid);
                }
            }

            if(M <= result) min = mid + 1;		// 자른 값이 크거나 같으면 최솟값을 움직여 중앙값 다시 계산
            else max = mid - 1;				// 작다면 최댓값을 움직여 중앙값 다시 계산
        }

        System.out.println(max);

        br.close();
    }
}