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

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

2805번: 나무 자르기

문제 풀이

이 문제도 입력 조건을 보면 범위가 상당히 크기 때문에 순차탐색이 아닌 이분탐색을 통해 아웃풋을 구해야 한다.

'M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.' 즉 M미터를 가져가기 위한 절단기의 높이는 여러 개가 나올 수 있고 이 중 최댓값을 구해야 하므로 upper bound 이분 탐색을 적용한다.

 

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class b2805 {
    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[] woods = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int left = 0;
        int right = Arrays.stream(woods).max().getAsInt();
        while (left < right) {
            int mid = (right + left) / 2;
//            long len = (long)Arrays.stream(woods).map(x -> x - mid).filter(x -> x > 0).sum();
            long len = 0;
            for (int wood : woods) {
                if (wood - mid > 0) {
                    len += wood - mid;
                }
            }

            if (len < m) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left-1);

    }
}

코드 풀이

몇 십분 동안 삽질한 코드이다.

//            long len = (long)Arrays.stream(woods).map(x -> x - mid).filter(x -> x > 0).sum();

long len = 0;
for (int wood : woods) {
    if (wood - mid > 0) {
        len += wood - mid;
    }
}

다음 코드는 작동 원리는 똑같다. 하지만 이 문제에선 값이 다르게 들어갈 때가 있다.

먼저 len은 나무 높이에 대해 자르고 남은 길이를 뜻한다. 나무 높이는 최대 10억까지 나올 수 있고 나무는 1백만 개 나올 수 있으므로 len은 long 타입이어야 한다. 위 스트림,람다 코드도 이를 인지하고 작성했지만 결과값 자체가 int형이기 때문에 아무리 형변환을 해줘도 이미 오버플로우가 발생한 값에 대해 형변환을 해주기 때문에 이상한 값을 반환한다.

 

이를 테스트 했던 코드이니 결과값만 확인해도 좋다.

int[] woods = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int mid=0;
long len = Arrays.stream(woods).map(x -> x - mid).filter(x -> x > 0).sum();
long len2 = 0;
for (int wood : woods) {
    if (wood - mid > 0) {
        len2 += wood - mid;
    }
}

System.out.println("len2 = " + len2);
System.out.println("len = " + len);