[Baekjoon] 2805 - 나무 자르기

📝 문제

 

 

🔑 풀이 과정

· 나무의 수가 10^6, 높이가 10^9이므로

높이를 1부터 10^9까지 모든 경우를 따져서 계산하면 (10^6) * (10^9)이므로 시간초과가 날 것이다.

그러므로 이분탐색을 사용해서 적절 길이를 찾을것이다.

(사실 이렇게 적었지만 문제를 딱 봤을때는 어떻게 해야할지 잘 모르겠다. 최소 최대 범위가 정해져있고 시간이 초과날 것 같으면 이분탐색 하면 되나?)

 

· 또한 각 나무의 높이가 10^9이고, 나무 개수가 10^6이므로 잘려진 나무의 길이를 구하는 변수는 int가 아닌 long이 되어야 한다.

 

· start = 1, end = 입력받은 나무 중 가장 높은 나무 길이, middle = (start + end) / 2 를해서 이분탐색을 한다.

만약 잘려진 길이가 가져가려는 길이보다 크면 일단 현재 middle값이 정답이 될 수도 있으므로 값을 저장해주고, 높이를 조금 더 높여서 잘른다. (start = middle + 1)

만약 잘려진 길이가 가져가려는 길이보다 작으면 높이를 낮춰서 잘라줘야 한다. (end = middle - 1)

 

· 이분 탐색을 너~무 오랜만에 해서 그런지 약간 실수했다. middle 값이 조건에 안맞으면 그 값도 제외를 해서 end = middle -1 을 하던지, start = middle + 1을 해줘야 하는데, -1, +1 연산을 안하고 middle값까지 포함해서 오답이 발생했었다.

 

· 또한 문제풀이에는 정답이 없음을 깨닫게 해 준 문제. 다른 분들은 뭐 마지막 답 출력할 때 start -1? end -1? 이런식으로 계산을 해주었던데, 아무리 해도 반례가 풀리지도 않았고 이해도 안됐다. 그래서 마지막으로 결국 내가 원하는 방식으로 answer 변수를 따로 두어서 조건을 만족할 때 값 저장을 하는 방식으로 풀이했더니 통과가 됐다.

 

· 그리고 나무 길이 중 최대 길이를 구할 때, 굳이 다 입력받고 배열을 정렬해서 구하는 방식으로 하지말고 입력 받을때 최댓값을 구하는 방식으로 진행하자. 혹시모를 시간초과가 날 수도 있다.

 

 

 

🔓 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //나무의 수
        int M = Integer.parseInt(st.nextToken()); //나무의 길이

        int[] trees = new int[N];

        st = new StringTokenizer(br.readLine());
        int max = Integer.MIN_VALUE; //나무 중 최댓값을 저장
        for(int i = 0; i < N; i++){
            trees[i] = Integer.parseInt(st.nextToken());

            max = Math.max(trees[i], max);
        }
        //입력종료

        //이분탐색 시작
        int start = 0;
        int end = max;
        int middle = 0;

        int answer = 0;
        while(start <= end){
            middle = (start + end) / 2;

            long sum = 0;

            for(int i = 0; i < N; i++){
                if(trees[i] - middle > 0)
                    sum += (trees[i] - middle);
            }

            if(sum >= M){
                answer = middle;
                start = middle + 1;
            }
            else{
                end = middle - 1;
            }
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 이분 탐색

- 매개 변수 탐색