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

 

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

2805번: 나무 자르기

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

이 전의 랜선 자르기 문제와 매우 유사한 문제다.

만약 직전 문제를 안풀어보셨다면 먼저 풀고오는 것을 추천한다. 그러면 이 문제도 자연스럽게 바로 풀릴 것이다.

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 번 문제는 앞서 언급했듯 랜선 자르기 문제와 풀이 방식이 거의 같은 문제다. 

 

이 문제를 풀기 전에 되도록이면 아래 글을 먼저 보고 오시는 것을 추천한다. 모두 다 연계되는 내용이기에 많은 도움이 될 것이다.

 

https://st-lab.tistory.com/269

[백준] 1654번 : 랜선 자르기 - JAVA [자바]

 

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

 

 

 

 

그럼 본격적으로 문제를 풀어보자.

 

일단, 랜선 자르기와는 무엇이 다를까?

자르는 것은 랜선자르기와 별반 다를게 없지만, 한 가지 다른 점이 있다. 바로 자르는 위치를 기준으로 기둥 부분이 아닌 잘린 위치의 윗 부분이라는 것이다.

 

 

쉽게 말하자면 이렇다는 것이다.

 

 

 

 

위와 같이 나무가 있다고 가정할 때, 우리가 잘라서 가져가고자 하는 길이(M)은 20m 이다.

 

 

 

 

그러면 먼저, 0m와 가장 높은 나무의 높이인 46m의 중간값인 23m를 기준으로 잘라보자.

 

 

 

보면 자르고 난 뒤의 가져가야 할 부분은 윗 부분이다.

그런데, 위 그림에서 볼 수 있듯 우리가 자른 나무들의 길이 합(sum)이 가져가고자 하는 길이(M)보다 크다.

 

그러면 자르는 높이를 낮춰야 하는가 높여야 하는가? 높여야한다.

즉, 일반적으로 표현하자면 하한선(lo 혹은 min변수)을 높여야 한다는 의미다.

 

 

 

그러면 46m와 24m의 중간 값을 계산해보면 35m 이니, 다시 35m로 잘라보자.

(23m는 이미 넘는 다는 것을 확인 했기 때문에 23m에 +1 을 한 값이 하한선이 된다.)

 

 

 

35m로 잘라도 마찬가지로 잘린 나무 길이의 합이 갖고가고자 하는 길이보다 크다.

 

그러면 다시 46m와 36m의 중간 값인 41m로 잘라보자.

 

 

 

 

이 번에는 잘린 나무의 길이가 가져가려는 나무의 길이보다 너무 작다.

 

그러면 어떻게 해야겠는가? 자르려는 높이를 낮춰야하지 않겠는가?

즉, 기존 하한선인 36m는 그대로 둔 채 상한선인 46m를 낮춰야 한다는 것이다.

 

즉, 두 값의 중간 값인 38m로 잘라보아야 한다.

 

 

 

위 이미지에서도 자른 합이 가져가려는 길이보다 작으므로(=자르는 높이가 높으므로) 상한선을 낮추어 36m과 38m의 중간 값인 37m로 다시 잘라본다면 다음과 같다.

 

 

 

 

역시나 자르는 높이가 높으니 상한선을 또 낮춘다면 36m와 37m의 중간 값인 36m (소수점 버림)로 잘라야 할 것이다.

 

 

 

 

이렇게 M과 sum이 같아지면 하한선을 높여서 36 + 1 = 37m가 되고, 그러면 다음 반복문에서 하한선이 상한선보다 커지면서 더이상 이분탐색을 하지 않고, 37m를 반환하게 된다.

 

즉, UpperBound 방식을 사용하여 하면, 원하는 탐색값의 +1이 되기 때문에 실제로 만족하는 값은 Upper Bound를 통해 반환 된 값의 -1을 한 값이 만족하는 값이 된다.

(나무를 최소한으로 자르기 위해서 어떤 예외가 있을지 모르기 때문에 Lower Bound가 아닌 Upper Bound 형식을 쓰는 이유이기도 하다.)

 

 

이러한 원리로 풀면 된다.

 

 

보면 랜선 자르기와 그렇게 다르지 않다고 느껴지지 않는가..?

 

 

그러면 코드 자체도 그리 어렵지 않을 것이다. 한 번 이분탐색으로 풀어 보자.

 

/*
 * [upper bound 방식]
 * int[] tree : 입력받은 나무들의 높이가 저장되어있는 배열(정렬할 필요 없음)
 * min : 하한선 변수로 초기값은 0
 * max : tree 에 저장 된 나무들 중 가장 큰 나무의 높이
 */

while(min < max) {

	// 중간 값(=자르는 위치)을 구한다.
	int mid = (min + max) / 2;
	long sum = 0;


	for(int treeHeight : tree) {
				
		/*
		 *  tree의 잘린 길이 = tree의 높이 - 자르는 위치(mid)
		 *  tree의 잘린 길의의 합을 구한다.
		 *  이 때 자르는 위치가 주어진 나무의 높이보다 클 수 있기 때문에
		 *  0 이하인 경우(=음수)에는 합산을 하지 않고 양수만 합산하도록 해야한다.
		 */
		if(treeHeight - mid > 0) { 
			sum += (treeHeight - mid);
		}
	}
			

	/*
	 * 자른 나무 길의의 합이 M보다 작다는 것은
	 * 자르는 위치(높이)가 높다는 의미이므로 높이를 낮춰야 한다.
	 * 즉, 상한(max)를 줄여야 한다.
	 */
	if(sum < M) {
		max = mid;
	}
			
	/*
	 * 자른 나무 길이의 합이 M보다 크다는 것은
	 * 자르는 위치(높이)가 낮다는 의미이므로 높이를 높여야 한다.
	 * 또한, 같을 경우에는 최대한 적게 자르기 위해 자르는 높이를
	 * 높여야 하므로 하한(min)을 올려야 한다.
	 */
	else {
		min = mid + 1;
	}
}

// 출력할 결과 값 : min - 1

 

 

위와 같이 매 탐색마다 배열의 원소들을 순회하면서 해당 나무들에서 자르는 높이(mid)를 빼주어 합을 구해야 한다.

 

단, 중요한 점은 자르는 높이(mid)보다 나무의 높이가 더 낮은 경우에는 음수 값이 나온다. 하지만, 음수값을 합산하는 것이 아닌, 못자르는 나무는 잘린 길이가 0m 로 봐야하기 때문에 양수일 경우에만 합산을 해주는 것만 따로 처리를 해주어야 한다.

 

또한 단일 나무의 길이가 최대 1,000,000,000 (10억) 이기 때문에 합산하는 과정에서 overflow가 발생하지 않도록 sum 변수는 int 타입이 아닌 long 타입으로 해주어야 한다.

 

이 부분들만 유의하면 그리 어렵지 않게 풀이할 수 있을 것이다.

 

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려 한다.

 

 

1. Scanner 

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int M = in.nextInt();
		
		int[] tree = new int[N];
		
		int min = 0;
		int max = 0;
		
		for(int i = 0; i < N; i++) {
			tree[i] = in.nextInt();
			
			/*
			 * 나무들 중 최댓값을 구하기 위해 매 입력 때마다 max 변수와 비교하여
			 * 입력 받은 나무가 max보다 클 경우 max 값을 해당 나무의 높이로 갱신해준다. 
			 */
			if(max < tree[i]) {
				max = tree[i];
			}
		}
		
		// 이분 탐색 (upper bound)
		while(min < max) {
			
			int mid = (min + max) / 2;
			long sum = 0;
			for(int treeHeight : tree) {
				
				/*
				 *  tree의 잘린 길이 = tree의 높이 - 자르는 위치(mid)
				 *  tree의 잘린 길의의 합을 구한다.
				 *  이 때 자르는 위치가 주어진 나무의 높이보다 클 수 있기 때문에
				 *  0 이하인 경우(=음수)에는 합산을 하지 않고 양수만 합산하도록 해야한다.
				 */
				if(treeHeight - mid > 0) { 
					sum += (treeHeight - mid);
				}
			}
			

			/*
			 * 자른 나무 길의의 합이 M보다 작다는 것은
			 * 자르는 위치(높이)가 높다는 의미이므로 높이를 낮춰야 한다.
			 * 즉, 상한(max)를 줄여야 한다.
			 */
			if(sum < M) {
				max = mid;
			}
			
			/*
			 * 자른 나무 길이의 합이 M보다 크다는 것은
			 * 자르는 위치(높이)가 낮다는 의미이므로 높이를 높여야 한다.
			 * 또한, 같을 경우에는 최대한 적게 자르기 위해 자르는 높이를
			 * 높여야 하므로 하한(min)을 올려야 한다.
			 */
			else {
				min = mid + 1;
			}
		}
		
		System.out.println(min - 1);
		
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

만약 비트 시프트 원리에 대해 이해하고 있다면 (min + max) / 2 대신 (min + max) >>> 1 으로 바꿔도 된다.

다만, 여기서는 쉽게 이해할 수 있도록 나눗셈 연산자를 사용하도록 하겠다. 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M 및 입력되는 나무들을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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());
		int M = Integer.parseInt(st.nextToken());
		
		int[] tree = new int[N];
		
		int min = 0;
		int max = 0;
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			tree[i] = Integer.parseInt(st.nextToken());
			
			/*
			 * 나무들 중 최댓값을 구하기 위해 매 입력 때마다 max 변수와 비교하여
			 * 입력 받은 나무가 max보다 클 경우 max 값을 해당 나무의 높이로 갱신해준다. 
			 */
			if(max < tree[i]) {
				max = tree[i];
			}
		}
		
		// 이분 탐색 (upper bound)
		while(min < max) {
			
			int mid = (min + max) / 2;
			long sum = 0;
			for(int treeHeight : tree) {
				
				/*
				 *  tree의 잘린 길이 = tree의 높이 - 자르는 위치(mid)
				 *  tree의 잘린 길의의 합을 구한다.
				 *  이 때 자르는 위치가 주어진 나무의 높이보다 클 수 있기 때문에
				 *  0 이하인 경우(=음수)에는 합산을 하지 않고 양수만 합산하도록 해야한다.
				 */
				if(treeHeight - mid > 0) { 
					sum += (treeHeight - mid);
				}
			}
			

			/*
			 * 자른 나무 길의의 합이 M보다 작다는 것은
			 * 자르는 위치(높이)가 높다는 의미이므로 높이를 낮춰야 한다.
			 * 즉, 상한(max)를 줄여야 한다.
			 */
			if(sum < M) {
				max = mid;
			}
			
			/*
			 * 자른 나무 길이의 합이 M보다 크다는 것은
			 * 자르는 위치(높이)가 낮다는 의미이므로 높이를 높여야 한다.
			 * 또한, 같을 경우에는 최대한 적게 자르기 위해 자르는 높이를
			 * 높여야 하므로 하한(min)을 올려야 한다.
			 */
			else {
				min = mid + 1;
			}
		}
		
		System.out.println(min - 1);
		
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 33278136  -  방법 2 : BufferedReader

채점 번호 : 33278129  -  방법 1 : Scanner

 

 

당연하게도 BufferedReader 방식이 빠른 것을 확인 할 수 있다. 

 

---

• 정리

 

이 번 문제는 필자가 맨 처음 언급한 문제들을 이미 풀어보았다면 그렇게 어려운 문제는 아니였다.

이분 탐색은 찾고자 하는 것이 무엇인지, 탐색의 범위(혹은 대상)가 무엇인지만 잘 알아차린다면 금방 구현을 할 수 있다.

 

특히 이분 탐색 방식에 따라 중복값이 있다면 어떤 방식을 쓸지를 고민해야 할 필요가 있는데, 가장 쉬운 방법은 lower bound와 upper bound를 어디서든 공통적으로 쓸 수 있는 포맷을 작성해놓고 쓰면 매우 편리하다.

왜냐하면 같은 값을 도출해낸다 하더라도 미세한 부분에서 구현 방식이 조금씩 다르다. 예로들어 while 조건문을 (min <= max) 로 해놓고 이분 탐색 내의 중간값에 따른 경계선 조정 방식을 다르게 할 수도 있다.

 

이러한 점들 때문에 여러분 자신이 가장 이해하기 편한 방식으로 구현을 해놓고, 이를 기반으로 풀어나가는 것이 훨씬 문제를 수월하게 풀 수 있을 것이다.

 

혹여 어렵거나 이해가 안되는 부분이 있다면 언제든 답글 남겨주셔도 된다.