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

[백준 2805번 / Java] 나무 자르기코딩테스트/백준2023. 7. 19. 06:50@mag1c

Table of Contents

728x90

문제 풀이

Silver 2

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

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

풀이

Binary Search 중 Upper Bound를 이용한 문제

[알고리즘] Upper Bound, Lower Bound

서론 Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다. [알고리즘] 이진탐색(이분탐색) - Binary Search Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보

mag1c.tistory.com

최대 높이 값을 구해야 했기 때문에, 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);
    }
}

728x90