[백준] 2805 - 나무 자르기 (Java)

[백준] 2805 - 나무 자르기 (Java)

문제

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

풀이/후기

이코테 책에서 푼 문제와 유사해서

복습 느낌으로 금방 끝날 줄 알았는데,

삽질하는데 시간을 엄청 투자했다,,,

 

- 일단 처음 오답이 나온 부분은 long처리였다. 나무의 합 sum 은 long형태로 사용해야 한다.

이거 외에 별다른 오답 부분이 없는데 왜 자꾸 오답처리가 되는지 한참 고민했다.

결국 찾아낸 부분은 처음 start와 end 설정 부분이었는데,

내가 배열을 정렬한 후 arr[0] 과 arr[N-1]로 지정한 부분이 문제였다.

이렇게 지정하면 배열의 값이 하나인 경우 start와 end가 잘 작동하지 않게 된다.

그리고 내 처음 생각으론 start가 가장 짧은 막대 길이로 시작하는 줄 알았는데 0부터 시작해야한다는 점도 뒤늦게 깨달았다.

그래서 이 부분을 start는 0, end는 입력받을 때 찾아낸 max값으로 지정하고 제출하니 드디어 정답처리가 되었다,,ㅠㅠㅠ

 

추가적으로 계속 삽질하면서 이것저것 보다보니 테스트케이스를 직접 찾아내고 만들어서 푸는 사람들이 많았다.

난,, 언제쯤 예외 케이스를 혼자 생각해서 테스트할 수 있을까?ㅜㅜ

이것도 계속 연습해서 습관화 해야겠다!

 

코드

package BinarySearch;

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

public class Problem2805 {

	static int N, M;
	static int[] arr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(str.nextToken());
		M = Integer.parseInt(str.nextToken());
		arr = new int[N];

		long max = 0;
		str = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(str.nextToken());
			max = Math.max(max, arr[i]);
		}

		long start = 0;
		long end = max;

		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = 0;

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

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

		System.out.println(end);
	}

}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/40b4ec9f76ada83f1c74a6947d6a8713a3947fff

참고

https://bellog.tistory.com/106

예시 테스트케이스 포함
https://kim-coffee.tistory.com/32