백준 - 이분 탐색 2805번 나무 자르기 / 풀이, 오답

= 처음 접근 방법 (틀림) = 

이 문제는 시간 초과로 틀렸다.

 

https://byungil.tistory.com/210

백준 - 이분 탐색 1654번 랜선 자르기 / 풀이,오답

이 문제랑 접근 방법, 풀이까지 거의 일치한다고 보면 된다.

 

똑같은 문제인데 왜 틀렸을까... 좀 더 고민하고 응용 능력을 키워야겠다.

upperBound를 이용해서 해결하지 않았기 때문에 틀렸다.

 

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다.

이 문장만 보고, while (true)에 내가 잘랐을 때, 필요한 나무면 break; 형식으로 코드를 구현해서 틀렸다.

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

이 문장을 더 꼼꼼하게 보고 생각했으면 틀리지 않았을 것 같다.

 

= 해결 =

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
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()); // 나무의 수 n
        int m = Integer.parseInt(st.nextToken()); // 필요한 길이 m
 
        st = new StringTokenizer(br.readLine());
 
        int[] arr = new int[n]; // 나무의 높이를 담는 배열 arr
        long max = 0; // 절단기의 높이
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }
 
        long min = 0;
        long tree = 0;
 
        while (min < max) {
            tree = 0;
            long mid = (min + max) / 2;
 
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] - mid > 0) {
                    tree += arr[i] - mid;
                }
            }
 
            if (tree < m) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
 
        System.out.println(min - 1);
    }
}