[백준/BOJ] 2805번 : 나무 자르기 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

2805번: 나무 자르기

---

- 문제 -

 

난이도 실버 3 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

이분 탐색을 통해 풀면 크게 어렵지 않게 풀 수있다.

https://comain.tistory.com/250

[백준/BOJ] 1654번 : 랜선 자르기 (JAVA / 자바)

위 문제도 이분 탐색을 사용해 푸는 문제이다. 나무 자르기보다 시간도 넉넉하고, 범위도 좁다. 이분탐색에대한 간략한 설명도 적혀있으니 참고할 사람은 참고하길.

 

나무 자르기는 1초에 나무의 개수도 많다. 그렇다보니 하나 삐끗하면 바로 시간 초과가 발생한다. 필자도 무수한 시간초과의 전과를 두고.... 왔다....

 

나무길이 중 제일 큰 값을 구한다. 이분 탐색에 사용 할 변수 3개를 선언한다. start, end, mid로 선언했다.

start는 범위의 시작값인데 여기서는 0부터 시작한다. end는 미리 구해둔 제일 큰 값을 저장한다. mid는 중간값이기 때문에 start와 end의 합의 절반 값을 저장한다.((start + end) / 2).

 

이제 mid값으로 나무들을 자를 것이다. 그렇게 나온 나무들의 길이의 합이 필요한 나무의 길이가 나오는지 본다.

자르고 더할 때 주의할 점은 나무의 길이가 mid보다 작거나 같다면 그 나무들은 자르지 않고, 더하지도 않을 것이다.

mid가 5이고, 1 3 6 5 8이 있다면 1과 3과 5는 자르지도 계산하지도 않는다.

그렇게 나온 값이 필요한 나무의 길이보다 크다면, 더 많이 잘라야한다는 것이다. start에 mid + 1을 저장한다.

작다면, 덜 잘라야한다는 것이다. end에 mid -1을 저장한다.

같다라는 기준도 정해줘야 하는데 여기서 나무를 무조건 집에 가져간다고 한다. 대신 원하는 길이 이상이라고 한다. 그렇단건 필요한건 15인데 어떻게든 15가 잘라지지 않는다면 15보다 길게 잘리는 것중 15에 제일 가깝게 구하면 되는 것이다. 그렇기때문에 처음 start 에 mid + 1을 하는 범위에 크다면이 아니라 크거나 같다면으로 조건을 해주고, 결과 변수에 mid값을 저장한다.

위 행동을 범위가 0이 될때까지 반복한다.

 

코드를 보자.

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] arr = new int[N];
		int max = 0;
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(max < arr[i]) max = arr[i];
		}
		
		int start = 0;
		int end = max;
		int mid = (end + start) / 2;
		int result = 0;
		//이분탐색 범위가 0이 될때까지 반복하는 반복문
		while(end - start >= 0) {
			//범위가 나무의 개수는 100만개이고, 길이는 20억 이상이라면 int형을 넘어선다.
			//합은 long형으로 구한다.
			long sum = 0;
			for(int i = 0; i < N; i++) {
				if(arr[i] > mid) sum += (arr[i] - mid);
			}
			
			if(sum >= M) {
				start = mid + 1;
				result = mid;
			}else if(sum < M) {
				end = mid - 1;
			}
			mid = (end + start) / 2;
		}
		System.out.println(result);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.