99클럽 코테 스터디 6일차 TIL 이분탐색(나무 자르기)

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

 

이분탐색 문제를 여러개 풀다보니 이제 문제를 읽으니까 언제 이분탐색을 써야할지 감이 살짝 온다

1. 변수 범위가 클 때! (1억 이상)

2. 구해야하는 값이 랜덤이 아닌, 특정 기준에 맞춰 지속적으로 범위를 찾아주어야 할 때! 즉 문제에서 구하는 값이 최대, 최소인 경우

큰 범위 내에서 특정 값을 범위를 통해 찾아야 할 때 => 이분탐색을 쓰자!

 

무튼 이 문제는 전에 풀었던 예산과 비슷하게 풀었는데 2%에서 틀려서 당황했다,,

여러 테케 만들어서 넣어봐도 다 분명 정답이 나오는데,, 문제는 자료형이었다!!!

나무의 길이 M이 최대 20억인데 calc 함수에서 상근이가 집으로 가져가려고 하는 나무의 길이 result가 int형 범위를 넘어가는 것이었다.

그래서 long으로 바꿔주니 바로 통과!!

 

***자료형 제발 신경 쓰자!!!!!!!!!***

 

<제출 코드>

package STUDY;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Day06_BOJ_2805 {

    static int n, m;
    static int ans;
    static int[] arr;

    public static long calc(int mid){
        long rest = 0;
        for(int i=0; i<n; i++){
            // 절단기에 설정한 값보다 큰 나무
            if(arr[i] > mid){
                rest += (arr[i] - mid);
            }
        }
        return rest;
    }

    public static void binarySearch(int s, int e){
        if(s > e) return;
        int mid = (s + e) / 2;

        long rest = calc(mid);
        if(rest >= m) {
            ans = Math.max(ans, mid);
            binarySearch(mid+1, e);
        }
        else binarySearch(s, mid-1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        int tall = 0;
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            tall = Math.max(tall, arr[i]);
        }
        binarySearch(1, tall);
        System.out.println(ans);
    }
}