[백준 2805번 / Java] 나무 자르기

문제 풀이

Silver 2

 

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

2805번: 나무 자르기

 

 

 

 

풀이

Binary Search 중 Upper Bound를 이용한 문제

[알고리즘] Upper Bound, Lower Bound

[알고리즘] Upper Bound, Lower Bound

 

 

최대 높이 값을 구해야 했기 때문에, Upper Bound를 사용했다.

 

1. 음수일 경우를 배제해야한다.

2. max는 tree 배열 입력 시 가장 긴 tree의 길이로 선정

3. overflow를 대비한 length의 타입을 long으로 설정.

int left = 0;
int right = max;

while(left < right) {
    int mid = (right + left) / 2;
    long length = 0;

    for(int tree_len : tree) {
        //음수일 경우 포함하면 안됨
        if(tree_len - mid > 0) length += tree_len - mid;
    }

    //upper bound
    if(length >= M) left = mid + 1;

    else right = mid;
}

System.out.println(left - 1);

 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] tree = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        int max = 0;
        for(int i = 0; i < N; i ++) {
            tree[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, tree[i]);
        }

        int left = 0;
        int right = max;

        while(left < right) {
            int mid = (right + left) / 2;
            long length = 0;

            for(int tree_len : tree) {
                //음수일 경우 포함하면 안됨
                if(tree_len - mid > 0) length += tree_len - mid;
            }

            //upper bound
            if(length >= M) left = mid + 1;
            else right = mid;
        }

        System.out.println(left - 1);
    }
}