[JAVA][백준 2805] 나무 자르기

 

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

 

 

---

풀이 과정

일단 문제를 읽어보면 절단기 높이 H를 지정해서 그 단위로 목재를 자르고 떨어져나간 목재를 가져가는 방식이다.

그 목재가 M미터가 되도록 최소한 환경을 생각해서 잘라간다는 내용인데...

1. 일단 입력값 중 최대값을 찾아

2. 그 값을 기준으로 점점 줄이든 늘리든 H를 설정하고

3. 잘려나간 나무의 길이가 M이상인지 보는 문제 같다

 

H를 설정하는게 이 문제의 관건 같은데 나무의 최대 높이가 20억이기 때문에 길이를 하나씩 줄여가면서 보는건 좀 무리인 것 같다.

최대 N* M 정도 될 것 같은데 그 값이 만만치가 않다.

(근데 그냥 최대 높이가 20이라고 해도 20부터 1까지 1씩 줄여가면서 보는건 좀....노가다스럽긴 하다.. 이런 코드 짜면 컴퓨터한테 미안해야할듯)

 

그래서 생각한 것이 이분탐색 

나는 대부분의 문제에서 그냥 인덱스를 탐색을 쭉 해야하는데 수가 너무 크면 반씩 잘라서 보는 이분탐색을 하면 좀 효율적이지 않을까 생각이든다.

왜냐하면 솔직히 우리도 처음부터 끝까지 보기 싫으니깐 일상생활에서도 무의식적으로 이분탐색 같은거 많이 하잖아요?

그래서 슬쩍 알고리즘 분류를 봤는데 이분 탐색이라고 써있길래 이분 탐색으로 풀기 도전

 

내가 생각한 풀이 방법으로는

1. 1에서부터 주어진 나무 길이의 최대값의 중간 값((0 + 최대값)/ 2)이 h가 되도록한다.

2. h로 나무를 잘랐을 때 남는 길이가 더 크면 1~h의 중간값으로 같은 과정을 반복하고 남는 길이가 더 작으면 h~최댓값의 중간값을 찾아 들어가는 방식으로 풀려고 한다. 

 

 

그래서 열심히 풀었는데 채점 결과 틀렸다...

 

↓ 틀린 코드

처음 제출한 코드.

 

// Parametric Search

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

public class S_2805 {
    public static void main(String[] args) throws Exception {
        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[] arr = new int[N];
        int max = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }

        int left = 0;
        int right = max;
        int answer = 0;
        while(left <= right) {
            int m = (left + right) / 2;
            int sum = 0;
            for (int i = 0; i < N; i++) {
                if (arr[i] > m) {
                    sum += arr[i] - m;
                }
            }

            // 너무 많이 잘랐을 경우 높이를 좀 더 높게 해야함.
            if (sum >= M) {
                answer = m;
                left = m + 1;
            } else {
                right = m - 1;
            }
        }

        System.out.println(answer);
    }
}

어디가 틀린걸까 고민을 열심히 해봤는데 일단 테스트케이스는 잘 나온다.

보통 이런경우 내가 문제를 제대로 안읽어서 힌트를 놓친 경우가 많아서 다시 문제를 읽어보기로 했다.

그 중 제일 먼저, 처음부터 마음에 걸렸던 입력값을 보기로 했다.

나무의 최대 높이는 10억, 상근이가 필요로 하는 나무의 길이는 20억
이 정도 되면 항상 변수를 int로 할지 long으로 할지 고민해야된다.

 

요구되는 나무의 양이 M이라면 중간값을 조정하는 과정에서 sum이 21억보다 많이 나오게 되는 경우가 발생한다.

내 코드는 sum이 int로 되어있어 너무 많이 자르게 되면 값이 제대로 안나오기 때문에 2퍼에서 틀린 것 같다.

그래서 sum을 long으로 바꿨더니 바로 통과~~

 

항상 틀리고 나서 고민해보는 습관... 좋지 않은 것 같다.

문제가 일어나고 나서야 허둥지둥 고치는 미래의 내가 보인다...,.

 

시간이 다른 사람들보다 더 많이 걸리길래 봤더니 그 사람들은 input을 받을때 이미 만들어진 reader 클래스를 사용하는 것이 아니라 직접 짠 코드로 input을 받는 것 같았다. 일단 알고리즘 공부가 목표기 때문에 이 부분은 패스...

 

이 문제는 사실 공유기 설치라는 문제가 이해가 안되서 더 쉬운 문제인 나무자르기 문제를 푼 것이었다.

똑같은 문제라고 하는데 나무자르기는 쉽게 풀 수 있었다. 
공유기 설치도 풀어보러 가야지

---

풀이

// Parametric Search

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

public class Main {
    public static void main(String[] args) throws Exception {
        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[] arr = new int[N];
        int max = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }

        int left = 0;
        int right = max;
        int answer = 0;
        while(left <= right) {
            int m = (left + right) / 2;
            long sum = 0;
            for (int i = 0; i < N; i++) {
                if (arr[i] > m) {
                    sum += arr[i] - m;
                }
            }

            // 너무 많이 잘랐을 경우 높이를 좀 더 높게 해야함.
            if (sum >= M) {
                answer = m;
                left = m + 1;
            } else {
                right = m - 1;
            }
        }

        System.out.println(answer);
    }
}