백준 2805. 나무자르기

🅰 백준 2805. 나무자르기

2805번: 나무 자르기

✏️ 문제 풀이

• 이분탐색을 이용하여 정답이 되는 값을 도출해내는 문제이다.
• start값을 0, end값을 N개의 나무중 최고 높이의 값, mid = (start+end)/2 로 설정해주었다.
• 재귀함수의 기저조건으로 start>end 이면 결과값을 출력해주었고
• for문안에서 각 나무들과 mid의 차이가 0보다 크면 상근이가 가져갈 수 있는 height 값에 더해주었다.
• height값과 M을 비교하여 height>=M이면 start와 mid값을 최신화시켜주었고
• height<M이면 end와 mid값을 최신화시켜줘서 재귀를 반복해주었다.

✏️ 소스코드

package binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_실버3_2805_나무자르기 {
	private static int N, M; 
	private static long tree[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 데이터 입력
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		long end = 0;
		tree = new long[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			tree[i] = Integer.parseInt(st.nextToken());
			if (tree[i] > end) // 입력 최대값 end로 설정
				end = tree[i];
		}
		// 이분탐색을 위한 start,mid 설정
		long start = 0;
		long mid = (start + end) / 2;
		recur(start, mid, end);
	}
	// 재귀함수 반복
	private static void recur(long start, long mid, long end) {
		// 기저조건
		if(start>end) {
			System.out.println(mid);
			return;
		}
		
		// 가져갈 수 있는 높이 저장
		long height = 0;
		for (int i = 0; i < N; i++) {
			if(tree[i]-mid>0) {
				height += tree[i]-mid;
			}
		}
		
		// 높이가 M보다 크거나 같을 때
		if(height>=M) {
			start = mid+1;
			mid = (start+end)/2;
		}
		// 높이가 M보다 작을 때
		else {
			end = mid-1;
			mid = (start+end)/2;
		}
		// 재귀 반복
		recur(start,mid,end);
	}
}

 

✅ 후기

• 이분탐색을 이용하여 어떻게 접근해야하는지 어려웠으나, start와 end값만 잘 지정해주면 답을 쉽게 해결할 수 있었다.
• 또한 데이터를 더하고 구하는 과정에서 int형의 범위를 넘어서서 long형으로 선언하여서 문제를 해결하였다.