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

문제 (이진 탐색)

 

2805번: 나무 자르기

 

 

문제 풀이

 

이진 탐색 알고리즘은 알고 있었지만 이 문제를 통해 이와 비슷한 새로운 알고리즘을 알게되었다.

 

✔️이진 탐색

: 데이터가 정렬되어 있는 배열에서 특정값을 찾아내는 알고리즘

1) 중간에 있는 임의의 값을 선택하여 찾고자 하는 수 X와 비교한다

1-1) X가 임의값보다 작으면, 임의값 기준 왼쪽 데이터들을 대상으로 다시 탐색

1-2) X가 임의값보다 크면, 임의값 기준 오른쪽 데이터들을 대상으로 다시 탐색

 

✔️파라메트릭 서치

: 주어진 범위 내에서 원하는 값 또는 조건에 일치하는 값을 찾아내는 알고리즘

1) 최적화 문제를 → 결정 문제로 바꾸어서 푸는 방식

최적화) 적어도 M미터의 나무를 벌목하기 위해 절단기에 설정할 수 있는 최대값

결정)    적어도 M미터의 나무를 가져가기 위해 절단기 값을 H로 할 수 있는가?

2) 결정에 대한 대답은 Yes or No

 

✔️알고리즘

1) 절단기가 설정될 수 있는 최소, 최대값의 범위 설정 (백준 예시 기준: 0~20)

2) 임의의 절단기 설정값 mid 설정 (mid값이 될 수 있는 범위는 0~20)

3) mid로 잘랐을 때 얻을 수 있는 나무의 총 길이 sum 구함

3-1) sum >= M 이면, 너무 많이 잘랐으므로 최소값의 범위를 mid+1로 올린다

3-2) sum < M 이면, 나무가 부족하므로 최대값의 범위를 mid-1로 내린다.

 

❗절단기 값을 설정해 나무를 잘라가는 값을 계산할 때, int형의 범위를 넘어갈 수 있어서 long타입으로 선언해줘야 함

 

소스 코드

 

public class b_2805 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int answer = 0;
		int N = sc.nextInt();	//나무 개수
		int M = sc.nextInt();	//가져가고자 하는 길이
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++)
			arr[i] = sc.nextInt();
		
		Arrays.sort(arr);
		
		int start = 0;
		int end = arr[N-1];
		int mid = 0;
		
		while(start <= end) {
			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;
				answer = mid;
			}
			else
				end = mid - 1;
		}
		
		System.out.println(answer);
		sc.close();
	}

}