[Algorithm] 백준 이분탐색 문제 - 나무 자르기(2805) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 나무 자르기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int[] trees;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        trees = new int[n]; // n개의 나무
        
        m = parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < n; i++) {
            trees[i] = parseInt(st.nextToken());
            max = Math.max(trees[i], max); // 가장 긴 나무를 선택하여 자를 위치 선정
        }
        
        System.out.println(find(max));
    }
    
    static long find(int max) {
        long value, left, mid; // 이분 탐색을 위한 long 값 20억 이상 될 수 있음
        long right = max; // right 최대값 선정
        value = left = mid = 0L; // value, left 초기화

        while(left < right) {
            mid = left + (right - left) / 2; // 이분탐색 중간 값 최대 40억

            for (int tree : trees) {
                if (tree > mid) value += tree - mid; // 잘리는 위치보다 큰 경우 더하기
            }
            
            if (value >= m) left = mid + 1; // 목표로 하는 값보다 같거나 크다면 upper bound
            else right = mid; // 아니라면 right
            value = 0; // value 초기화
        }
        
        return right - 1;
    }
}

 

2. 시간 복잡도 계산

 

이번 문제는 앞 서 풀었던 랜선 자르기와 비슷한 문제로 이분 탐색의 upper bound를 설정하여 해결할 수 있습니다.

최대 100만 개의 N을 가지고, 20억 개의 범위를 탐색해야 하므로 일반적으로 for문을 돌린다면 시간초과가 날 수 있습니다.

 

총나무의 수가 최대 100만 개이므로 찾은 최적의 값을 가지고 100만 번을 연산해야 합니다. 만약 아니라면 값을 바꿔서 다시 진행해야 하므로 100만 * 나무를 찾는 횟수가 시간 복잡도가 됩니다.

 

이분 탐색은 logM의 시간 복잡도를 가지므로. 이분 탐색의 upper bound를 활용한다면,

O(N * logM)  = O(100만 * 약 31) = 대략 O(3100만) 의 시간을 가진다고 볼 수 있습니다. 

 

3. upper bound로 계산하기

 

static long find(int max) {
    long value, left, mid; // 이분 탐색을 위한 long 값 20억 이상 될 수 있음
    long right = max; // right 최대값 선정
    value = left = mid = 0L; // value, left 초기화

    while(left < right) {
        mid = left + (right - left) / 2; // 이분탐색 중간 값 최대 40억

        for (int tree : trees) {
            if (tree > mid) value += tree - mid; // 잘리는 위치보다 큰 경우 더하기
        }
        
        if (value >= m) left = mid + 1; // 목표로 하는 값보다 같거나 크다면 upper bound
        else right = mid; // 아니라면 right
        value = 0; // value 초기화
    }
    
    return right - 1;
}

 

upper bound는 찾아야 하는 값 a에 가장 근접하게 큰 수를 찾도록 돕는 알고리즘입니다.

이분탐색을 수행하면서 경계점을 찾아야 하는 경우 사용할 수 있습니다.

 

mid의 값을 left + (right - left) / 2로 업데이트한 후, value가 크거나 같다면 left = mid + 1 하여 upper 경계를 올립니다.

value가 크거나 같다는 말은 충분한 양을 획득했다는 의미이므로 높이를 올려서 잘라야 하는 양을 줄이는 것입니다.

(기기의 높이를 올리면 잘리는 길이가 줄어듬)

 

반면, 작다면 right = mid로 수정하여 value를 증가시키는 방법으로 이분탐색을 진행합니다.

left가 right보다 같거나 커지는 시점이 오면 루프를 종료하고, upper의 경계를 설정했으므로 right의 값에서 -1을 하여 리턴합니다.

 

-1을 하는 이유는 다음과 같습니다.

left 35

right 37

mid 36 

value >= m

-> left = mid + 1;

left <= right 이므로 종료하게 됩니다. 여기서 right는 찾아야 하는 target의 값보다 1이 크게 되므로(자연수)

이와 같은 로직을 작성할 수 있게 됩니다.

 

이상으로 백준 나무 자르기 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!!