[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)2805번, 나무 자르기

문제 링크

2805번: 나무 자르기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이분 탐색이란 오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이분탐색에 자세한 내용은 링크를 남기겠습니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

예를들어(시작값 = 1, 최대값 = 9)

찾는 값 = 3, 중간값 = 5

1. 찾는 값이 중간 값보다 작으므로 최대값은 4가 된다.

1

2

3

4

5

6

7

8

9

시작값 = 1, 최대값 = 4 찾는값 = 3 중간값 = 2

2. 찾는 값이 중간 값보다 크므로 시작값은 = 3

1

2

3

4

5

6

7

8

9

시작값 = 3, 최대값 = 4 찾는값 = 3 중간값 = 33. 찾는 값과 중간값이 같으므로 3은 정렬된 숫자에 존재합니다.

1

2

3

4

5

6

7

8

9

이 문제에서는 이분 탐색을 이용해서 얻은 중간값의 높이만큼 나무를 잘랐을 때 필요한 나무의 길이를 구할 수 있는지를 확인하는 것이 문제에 핵심입니다.

 

나무를 자를 수 있는 범위는 가장 큰 나무에 따라 달라지기 때문에 최대값으로 설정하였습니다.

예제입력1에서는 높이가 가장 큰 20가 최대값이 되어서 0~20 범위에서 이분탐색을 진행할 것입니다.

 

여기서 자를 수 있는 높이의 최대값이므로 UpperBound를 구하는 공식을 사용할 것입니다.

UpperBound는 아래 문제에서 End로 표현하는 것을 참고하시면 감사하겠습니다.

[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)10816번, 숫자 카드 2

 

그래서 0~20 범위에서 이분탐색으로 중간값을 얻어서 나무들을 중간값으로 잘랐을 때 필요한 나무의 길이가 나오는지 확인하는 것을 반복하여 최대 자를 수 있는 높이를 얻어내는 것입니다.

 

예제입력1으로 진행되는 과정을 살펴보겠습니다.

랜선을 자를 수 있는 최대 길이 = 20, 최소 길이 = 0

0

~

20

1. 중간값은 (0+20)/2 = 10입니다.

나무들을 높이 10으로 잘라보겠습니다.

20	-10	= 10
15	-10	= 5
10	-10	= 0
17	-10	= 7

얻어낸 나무의 길이는 22개로 필요한 나무에 길이 7개보다 커서 이대로 잘라도 되지만 자를 수 있는 최대 높이를 구해야 하기 때문에 중간값보다는 높게 잘라봐야 합니다.

 

그래서 자를 수 있는 더 높은 길이는 최대길이 = 20, 최소길이 = 11

11

~

20

2. 중간값은 (11+20)/2 = 15입니다.

나무들을 높이 15으로 잘라보겠습니다.

20	-15	= 5
15	-15	= 0
10	-15	= 0
17	-15	= 2

얻어낸 나무의 길이는 7로 필요한 나무의 길이와 같습니다.

 

여기서 결과를 도출하는 것이 아닌 문제에서는 길이가 7이 되면서 자를 수 있는 최대의 길이를 구해야하기 때문에 이제부터는 최대로 자를 수 있는 나무의 높이를 구하는 것입니다.

15보다 자를 수 있는 더 큰 높이는 최대길이 = 20, 최소길이 = 16

16

~

20

3. 중간값은 (16 + 20) / 2 = 18입니다.

나무들을 18으로 잘라보겠습니다.

20	-18	= 2
15	-18	= 0
10	-18	= 0
17	-18	= 0

얻어낸 나무의 길이는 2이므로 필요한 나무의 길이보다 적으므로 더 작은 높이로 나무를 잘라야 합니다.

 

그래서 자를 수 있는 작은 길이는 최대길이 = 16, 최소길이=18

16

~

18

위 과정을 반복하여 최소길이가 최대길이보다 커질 때 최대길이가 필요한 나무의 길이를 구할 수 있는 최대로 자를 수 있는 값이 됩니다.

위 과정을 반복하고 마지막에는 범위는(최대길이 = 16, 최소길이 = 16)

16

~

16

결과적으로 최대길이 값 16이 출력됩니다.

하지만 UpperBound이기 때문에 마지막에 -1을 취해야해서 16-1로 15가 결과로 반환되도록 합니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 나무의 최대 길이를 구해서 자를 수 있는 최대값을 구하였습니다.

2. 범위(0 ~ 최대길이)에서 중간값을 구합니다.

3. 중간값을 통해 나무들을 잘라서 필요한 길이가 나오는지 확인합니다.

4. 필요한 길이가 나오면 중간값보다 더 큰 범위로, 나오지 않는다면 작은 범위로 이분탐색을 진행합니다.

5. 위 과정을 반복하여 최소길이가 최대길이보다 커졌을 때 최대길이-1를 반환합니다.

 

※중간값 구하는 공식 = (시작값 + 최대값) / 2

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 N과 M을 나누었습니다.
• 자를 수있는 최대높이/자를 때 나오는 길이를 구하는 treeHeight,heightCheck함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 자를 수 있는 최대높이를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• treeHeight함수에서 이분탐색에 UpperBound를 사용하여 최대값을 구하였습니다.
• heightCheck함수에서 중간값만큼 나무를 잘라서 얻을 수 있는 나무의 길이를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] tree;	//나무 높이 저장 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //------입력값 저장 및 배열 초기화-------
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        tree = new int[N];
        st = new StringTokenizer(br.readLine()," ");
        int max = Integer.MIN_VALUE;		//최대값
        for(int i=0;i<N;i++) {
        	tree[i] = Integer.parseInt(st.nextToken());
        	max = Math.max(max, tree[i]);
        }
        //-------함수 실행 및 결과 출력-------
        bw.write(treeHeight(max, N, M) + "\n");        
        bw.flush();
        bw.close();
        br.close();
    }
    //-----자를 수 있는 최대값 구하는 함수--------
    //UpperBound 이용
    public static long treeHeight(int max, int N, int M) {
    	long start = 0;
    	long end = max;
    	while(start<end) {
    		long median = (start + end) / 2;
    		long sum = heightCheck(median, N);
    		if(sum<M)
    			end = median;
    		else
    			start = median + 1;
    	}
    	return start-1;		//UpperBound 형태로 -1을 취해줌
    }
    //-------잘랐을 때 나오는 길이 구하는 함수--------
    public static long heightCheck(long height, int N) {
    	long result = 0;
    	for(int i=0;i<N;i++) {
    		long temp = tree[i] - height;
    		result += temp<0?0:temp;	//자르는 값이 해당 나무보다 높으면 0을 저장
    	}
    	return result;
    }

}