[백준 2805] 나무 자르기

 

 

이분탐색을 입문하기 좋은 문제이다.

 

예제로 풀이해보겠다.

 

나무의 높이는 20, 15, 10, 17 이고 최소값은 0, 최대값은 20이다.

최대값은 나무의 높이 중 가장 큰 것으로 해도 되고 문제에서 주어진 최대값 1000000000 을 사용해도 된다.

low	20	15	10	17	high
0					20

 

정한 low, high 을 2등분 하여 조건을 성립하는 방향으로 범위를 좁혀가야 한다.

 

0과 20의 중간값은 10 이므로 10의 높이로 나무를 자른다.

 

low	20	15	10	17	high
0	10	5	10	7	20

 

각 나무는 10, 5, 10, 7 의 길이만큼 남았고 자른 나무는 10, 10, 0, 10 으로 총 30이다.

나무는 적어도 7만큼 가져갈 것이므로 30은 너무 크다.

따라서 자를 높이를 올려야 하므로 low 값을 중간값 만큼으로 올려서 다시 계산한다.

 

low	20	15	10	17	high
10	5	0	0	2	20

 

low = 10, high = 20 이므로 15의 높이에서 나무를 잘랐다.

나무는 5, 0, 0, 2 만큼 남아 7이 되어 답을 벌써 찾았다.

하지만 문제에서는 적어도 7 만큼을 얻는다고 하였으므로 만약 7만큼 자를 경우가 없다면 답이 8이 될수도 있다.

자른 나무의 총 길이 >= M 이므로 low 값을 또 올려서 계산한다.

 

low	20	15	10	17	high
15	3	0	0	0	20

 

자른 나무의 총 길이 < M 이므로 high 값을 내린다.

 

low	20	15	10	17	high
15	4	0	0	1	17

 

역시 high 값을 내린다.

 

low	20	15	10	17	high
15	5	0	0	2	16

 

low 와 high 가 1 차이날때 까지 반복하면 가장 최적의 답을 찾을 수 있다.

물론 low, high 의 값을 바꾸는 연산에 따라 반복문이 끝나는 조건도 바뀔 수 있다.

 

 

코드 1 (위에 설명한 내용)

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int low = 0;
        int high = 1000000000;
        while(low + 1 < high) {
            int mid = (low + high)/2;
            long sum = 0;
            for(int i=0; i<n; i++)
                if(a[i] > mid) sum += a[i] - mid;
            if(sum >= m) low = mid;
            else high = mid;
        }
        System.out.println(low);
    }
}

 

 

코드 2

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int low = 0;
        int high = 1000000000;
        while(low <= high) {
            int mid = (low + high)/2;
            long sum = 0;
            for(int i=0; i<n; i++)
                if(a[i] > mid) sum += a[i] - mid;
            if(sum >= m) low = mid + 1;
            else high = mid - 1;
        }
        System.out.println(high);
    }
}

 

 

여러 문제를 풀어봤는데, 두번째 코드가 예외처리 하기 더 좋은것 같다.