[백준문제풀이] 2805 나무자르기 java

너무너무 먼길을 돌아왔다 크아아악!!!!

덕분에 .... 이분탐색이랑 매개변수탐색 문제가 나오면 자신있게 풀 수 있을것같다.

 

접근법 : 

1) 어떻게 풀 것인가?

이 문제는 알고리즘 수업을 듣던 중 풀게 된 문제이다.

알고리즘 수업을 들으면서 실패인채로 넘어가게 된 문제들이 있는데 이 문제가 그 중 하나였다. 

그 당시 문제의 '적어도' 라는 낱말을 놓쳐서 + 배열을 오름차순으로 해놓고 코드를 내림차순 기준으로 짜서...etc

(왜 그랬지..? 지금 생각해보면 어이없다 정신차리자!!) 틀린 후 안 건드린 문제다.......

이 문제의 시간복잡도와 공간복잡도, 그리고 문제의 키워드 ' 최댓값' 을 통해서

 이진탐색과 매개변수탐색으로 풀어야함을 알 수 있다.

 

2) 시간복잡도

. 나무의 개수 N : 1 ≤ N ≤ 1,000,000

  내가 원하는 나무의 길이 M : 1 ≤ M ≤ 2,000,000,000

  나무의 높이 H : 0≤H≤1,000,000,000

이므로, 만약 1초에 1억개를 계산한다고 할 때, N * log[2](H)로 풀어야 시간에 맞게 풀 수 있다.

중간에 시간초과가 나서 틀린게 하나 있는데 그건 시간 복잡도를 잘못계산해서 틀린 코드이다..

 

3) 공간복잡도

256mb이다.

처음에 공간복잡도를 생각안하고 풀었다가 메모리초과가 났다.

1) boolean배열을 새로 생성해 각 숫자마다 false, true값을 주고 true를 가지는 인덱스 중 가장 큰 인덱스를 return하는 방식

으로 하려했다가 메모리 초과가 났다. 

 

4) 풀면서 놓쳤던점

시간복잡도와 공간복잡도를 생각하지않은것

 

5) 이 문제를 통해 얻어갈 것

이분탐색과 매개변수탐색을 아주 잘...^_^ 알아간다.

 

import java.io.*;

public class Main {
    static int[] height; //트리 높이를 받는 arr
    static int n,m,max,resultmax;
    static long count;
    static int start,end;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        String[] strings = br.readLine().split(" ");
        n = Integer.parseInt(strings[0]);
        m = Integer.parseInt(strings[1]);
        max = 0;
        height = new int[n];
        String[] treestrings = br.readLine().split(" ");
        for(int i =0; i<n; i++) {
            height[i] = Integer.parseInt(treestrings[i]); //트리 높이
        }
        for(int a : height) {
            if(max <a) {
                max = a;
            }
        }
        start =0;
        end = max;
        resultmax = -1;
        parametic(0, max);
        System.out.println(sb);
    }
    static void parametic(int s, int e) {
        if(s<=e) {
            long mid = (s+e)/2;
            docut(mid);
            if(m<=count) {
                resultmax = Math.max(resultmax,(int)mid);
                start = (int)(mid)+1;
                parametic(start,end);
            }
            else{
                end = (int)(mid)-1;
                parametic(start, end);
            }
        }
        else{
            sb.append(resultmax);
        }
    }

    static long docut(long mid){
        count = 0;
        for(int a : height) {
            if((a - mid)>0) {
                count += (a - mid);
            }
        }
        return count;
    }
}