문제 2805 ( Java )

나무 자르기

 

매개 변수 탐색 기법을 적용하는 문제. 푸는 방법만 알면 간단하게 해결 가능합니다.

 

 

---

문제 풀이

 

1. 매개 변수 탐색을 위한 변수 설정

 

    찾아야하는 값은 자를 나무 길이의 최대값입니다. 이 최대값을 찾는데 매개 변수 탐색 기법을 적용해야하므로 left 변수 값에는 나무를 자를 수 있는 최소 길이, right 변수에는 나무를 자를 수 있는 최대 길이를 저장합니다. 나무의 높이는 0이상 1,000,000,000 이므로 left 에는 0을 저장하고 , right 변수에는 N개 나무들의 높이 중 가장 높은 키를 저장합니다.

 

 

2. 매개 변수 탐색

    이분 탐색 기법과 매우 비슷합니다. mid 값을 계산하고 mid 값이 조건에 참인지 거짓인지 판단한 후 left 값 혹은 right 값을 업데이트합니다.

 

 

값을 찾으면 출력합니다.

 

 

---

코드

 

import java.util.Scanner;
import java.util.Vector;
 
public class Main {
 
    static long N, M;
    static Vector<Long> v = new Vector<Long>();
 
    public static void main(String [] args) {
        
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextLong();
        M = sc.nextLong();
        
        long max = 0;
        
        for (long i = 0 ; i < N ; i++) {
            
            long temp = sc.nextLong();
            
            if ( temp > max) {
                max = temp;
            }
            
            v.add(temp);
        }
        
        long result = 0, left = 0;
        long right = max;
        
        while (left <= right) {
            
            long mid = (left + right) / 2;
 
            if (pos(mid)) {
                left = mid + 1;
                result = mid;
            }
            else
                right = mid - 1;
        }
        
        System.out.print(result);
    }
 
    public static boolean pos (long len) {
        
        long sum = 0;
        
        for (long i = 0; i < N ; i++) {
            
            long height = v.get((int)i);
            
            if ( height > len)
                sum += height - len;
            
            if (sum >= M)
                return true;
        }
        
        return false;
    }
}
 

---

결과