Baekjoon 문제 풀기 (2805번 : 나무 자르기) Java

2805번 : 나무 자르기

1. 문제읽기

---

잘랐을 때 나무 길이가 m과 같거나 큰 절단기의 높이의 최댓값 구하기

파이썬으로 풀었을 때와 정확히 똑같은 로직으로 짜서 실패했다.^^
이래서 틀린 문제를 다시 풀어보는 것이 중요하다는 것을 느꼈다..

2. 제출 코드

---

아래는 내가 제출했던 코드이다.
첫번째로 높이 값을 -1씩 해주면서 풀었는데 예상했던 대로 시간초과가 나와서, 이분 탐색을 써야한다는 것은 캐치했다.
그러나 m이 딱 떨어지지 않는 경우가 문제였다.(while문 조건도 덤..)
이분 탐색 알고리즘을 대충 쓸 줄만 알지 정확히 이해하지 못해 생긴 일이다.

고쳐야 하는 부분을 정리해보자면 아래와 같다.

1. 쓸데없는 변수

   cut은 mid를 사용하면 되므로 필요 X

2. 누적합 변수 자료형

   int를 long형으로

3. while문 조건에 = 붙이기

   왜 맨날 =을 뺄라고하는데?

4. 딱 떨어지지 않을 경우

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

public class BOJ2805 {
    public static void main(String[] args) throws IOException {
        // m보다 작으면 0
        // m보다 크면 x-m 만큼 가져감
        // 최대로 설정해서 딱 맞게 가져가기
        // 제일 큰 나무높이부터 1씩 줄이기
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String[] tmp = bf.readLine().split(" ");
        List<Integer> arr = new ArrayList<>();
        for(String i : tmp) {
            arr.add(Integer.parseInt(i));
        }
        Collections.sort(arr);

        int start = 0;
        int cut = arr.get(n-1);
        int end = cut;
        int ans = 0;  // 답 저장
        while(start < end) {
            int tree = 0;  // 임시 나무 높이
            int mid = (start+end)/2;
            cut = mid;
            for(int i = 0; i < n; i++) { // 가져갈 나무 높이 구하기
                if(arr.get(i) > cut) {
                    tree += arr.get(i) - cut;
                }
            }
            if(tree < m) {  // m보다 가져갈 나무 길이가 작으면
                //start = mid+1;
                end = mid-1;

            } else if(tree > m) { // m이 너무 높으면 기준 줄이기
                //end = mid-1;
                start = mid+1;
            } else {
                ans = cut;
                break;
            }
        }
        ans = cut;
        System.out.println(ans);
    }
}

3. 공부할 것

---

1) 쓸데없는 변수

cut변수를 없애고 mid를 cut대신 사용하여 하나로 통일했다.

2) 누적합 변수 자료형

파이썬과는 다르게 자료형의 최댓값도 신경써야 했는데, 나무의 누적 합계를 계산할 때 나무 길이가 최대 20억까지이므로 int형 최댓값(약 21억)을 금방 넘는다는 것을 예상할 수 있어야 한다.
따라서 누적합 변수의 자료형은 long형을 써야한다.

3) while문 조건에 = 붙이기

차근차근 생각해보면 start = end 조건이 없으면 이 조건일 때 검사를 하나 누락시키는 것이다.
왜 맨날 이분탐색 할 때마다 =을 빼는지 모르겠다…

4) 딱 떨어지지 않을 경우

아래 정답코드가 나에게는 더 직관적으로 이해가 가능했다.
m과 같은 높이를 찾으면 답을 출력하고 프로그램을 종료해버린다.(가장 정확한 답이므로)
같은 높이를 찾지 못하면 end가 답이 된다.
사실 end가 답이 되는 이유를 정확히 이해하지는 못했다. 적어서 풀어보니 그렇게 되기는 하는데 왜 그렇게 되는지 설명할 수는 없다.
더 문제를 많이 풀어보면 이해가 되는 날이 오겠지..
간단한 방법으로 아래와 같이 조건을 줘서 while문이 끝날 때까지 반복해주는 방법도 있다.

if(tree >= m) {
	start = mid+1;
} else {
	end = mid-1;
}
System.out.println(end);

정답 코드

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

public class BOJ2805 {
    public static void main(String[] args) throws IOException {
        // m보다 작으면 0
        // m보다 크면 x-m 만큼 가져감
        // 최대로 설정해서 딱 맞게 가져가기
        // 제일 큰 나무높이부터 1씩 줄이기 -> 이분탐색
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String[] tmp = bf.readLine().split(" ");
        List<Integer> arr = new ArrayList<>();
        for(String i : tmp) {
            arr.add(Integer.parseInt(i));
        }
        Collections.sort(arr);

        int start = 0;
        int end = arr.get(n-1);
        while(start <= end) {
            // mid = 자르는 높이
            long tree = 0;  // 임시 나무 높이
            int mid = (start+end)/2;
            for(int i = 0; i < n; i++) { // 가져갈 나무 높이 구하기
                if(arr.get(i) > mid) {
                    tree += arr.get(i) - mid;
                }
            }
            if(tree < m) {  // m보다 가져갈 나무 길이가 작으면
                end = mid-1;

            } else if(tree > m) { // m이 너무 높으면 기준 줄이기
                start = mid+1;
            } else {
                System.out.println(mid);
                System.exit(0);
            }
        }
        System.out.println(end);
    }
}