[Day06]JAVA- 백준 2805번 나무자르기

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

 

백준 2805번을 풀기 위해서는 이분탐색을 활용해야한다.

 

 

문제는 이분탐색 유형 중 간단한 편인다. 절단기의 최대 높이를 구하면 되는 것이다. 

 

- N : 나무의 수 

- M :  집에 가져가고자 하는 나무의 길

- mid : 절단기의 높이

 

나무들의 높이는  입력 받은 나무의 수(N) 으로 배열을 생성해준다 .

int[] tree = new int[N];

 

범위를 지정할때 left : 0 , right 는 입력받은 나무의 최대 높이로 지정해 주면 된다.

 for(int i=0;i<N;i++)
{   
    tree[i] = Integer.parseInt(st.nextToken());
    max= Math.max(max,tree[i]);
}

 

원하는 나무의 길이만큼 딱 맞아 떨어지는 경우도 있지만 아닌 경우도 생각해서 자른 나무의 길이의 합은 M 보다 크거나 같아야 한다. 

 

- tot : 잘린 나무들의 길이 합

 //절단한 후 남은 나무의 길이
for(int t : tree)
{
    if(t>mid)
        tot += t-mid; //가져갈 수 있는 총 나무 길이 구하기
}

 

두가지 경우를 생각해서 범위를 지정해 주는 것이다. 

 

1. 총 구해진 나무의 길이가 필요로 한 나무의 길이보다 작을 때 절단기의 높이를 줄여 더 많이 남도록 해야한다.

2. 총 구해진 나무의 길이가 필요로 한 나무의 길이보다 클 때 절단기의 높이를 높여 더 적게 남도록 해야한다. 

(절단기의 최대 높이를 구하는 것이니 딱 맞게 떨어져도 최대 높이를 구할 수 있도록 계속 끝까지 조회한다.)

 //구해진 길이가 원하는 길이보다 작으면 절단기의 높이를 줄여 더 많이 남도록 
if(tot < M)
    right = mid-1;         
else
{
    //구해진 길이가 원하는 길이와 같거나 클때 절단기의 높이를 높여 덜 남도록 
    left = mid+1;
    answer = Math.max(answer , mid);

}

 

 

* 최종코드 

import java.util.*;
import java.io.*;
public class Main{

public static void main(String[] args) throws IOException{       

    int answer=0;
    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];

   int max=0;

   st = new StringTokenizer(br.readLine()," ");
   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;
   int mid =0;
   long tot = 0;

   while(left<right)
   {
        System.out.println("왼쪽 : " + left +" 오른쪽  :" + right);

        mid = (left+right)/2; //절단기 높이
        System.out.println("절단기 높이 : " + mid);
        tot =0;

        //절단한 후 남은 나무의 길이
        for(int t : tree)
        {
            if(t>mid)
                tot += t-mid; //가져갈 수 있는 총 나무 길이 구하기
        }

        System.out.println("구해진 나무 길이 :" + tot +"\n");
        //구해진 길이가 원하는 길이보다 작으면 절단기의 높이를 줄여 더 많이 남도록 
        if(tot < M)
            right = mid-1;         
        else
        {
            //구해진 길이가 원하는 길이와 같거나 클때 절단기의 높이를 높여 덜 남도록 
            left = mid+1;
            answer = Math.max(answer , mid);

        }
    }

   		System.out.println("출력값 : " + answer);
	}
}

 

*결과 값