[CLASS 3: 이분탐색] 백준 2805 나무 자르기

✨ #오블완 #챌린지 #시작 ✨

 

챌린지 기간동안 코테를 하루에 한 문제씩 풀어보려 한다. ヾ(•ω•`)o 아자아자 !!!

 

 

 

2805번: 나무 자르기

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

 

# 코드

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

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());
        int[] arr = new int[n];
        int max = 0; // 가장 긴 나무의 길이
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        int start = 0;
        int end = max;
        int result = 0;
        while (start <= end) {
            int mid = (start + end) / 2;

            // 자른 나무의 합 sum 계산
            long sum = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] > mid) {
                    sum += arr[j] - mid;
                }
            }

            // sum 값에 따라 start, end 재설정
            if (sum >= m) {
                // 필요한 양보다 넉넉하게 잘린 경우
                result = mid; // 현재 값 저장
                start = mid + 1;
            } else {
                // 부족하게 잘린 경우
                end = mid - 1;
            }
        }

        System.out.println(result);
        br.close();
    }
}

• 이전에 비슷한 이분탐색 문제를 파이썬으로 풀어본 적이 있어 어렵지 않았던 문제였다.
• sum 값을 비교한다는 점이 조금 다르지만 기본 이분탐색 알고리즘은 동일하다.
• 나무의 길이를 입력받을 때 가장 긴 나무의 길이 max를 찾아놓고, 이후 이분탐색 시 0 ~ max 범위에서 자를 위치를 찾아가면 된다.
• 한 가지 sum 값을 long 타입으로 지정하는 부분만 조심하면 되겠다.

 

시간복잡도 나쁘지엑스

 

 

👇🏻 파이썬 이분탐색 문제풀이는 👇🏻

[이진 탐색] 백준 14627 파닭파닭