[백준] 통나무 자르기 - java

문제 설명 :

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

 

문제 요약 :

1. 가장 길이가 긴 통나무가 최소가 되도록 나무를 자르고 가장 길이가 긴 통나무의 길이 구하기
2. 가장 먼저 자른 나무의 위치 구하기

 

문제 풀이 시간 : 2시간

문제 성공 여부 : 실패

 

접근 방법(실패) :

1. 자를 수 있는 통나무 위치를 탐색하며 mid보다 통나무의 길이가 길어질 경우, cutCnt를 증가
2. cutCnt가 자를 수 있는 횟수보다 작거나 같을 경우 e 감소, 반대의 경우 s 증가
3. cutCnt가 자를 수 있는 횟수보다 작을 경우 가장 첫 번째 자를 수 있는 횟수 리턴(두 번째 정답 인자)
4. 같거나 클 경우, 최초로 자른 위치 반환

 

결론부터 적자면 내 접근방법은 정답에 가까웠다.

 

나도 이 방법 밖에 없는 것 같아 열심히 구현하였는데 시간압박 + 구현실력 부족으로 해결하지 못하였다.

 

따라서, 다른 고수분들의 코드를 참고하여 내가 이해한 대로 다시 풀어보았다.

 

접근 방법(성공) :

 

1. 이분 탐색

        while(s<=e){
            long mid = (s + e) / 2;
            int cutCnt = getCutCount(arr, mid, K, C);

            if(cutCnt <=C){
                ansLongest = Math.min(mid, ansLongest);
                ansFirst = firstCut;
                e = mid-1;
            }
            else{
                s = mid+1;
            }
        }

 

가장 핵심이 되는 이분 탐색 코드이다.

 

mid(가장 길이가 긴 통나무의 길이)를 계산하여 통나무를 몇번 잘라야 하는지 계산한다.

 

계산 후 cutCnt와 C(자를 수 있는 횟수)를 비교하여 이분 탐색을 이어간다.

 

cutCnt가 C보다 크다면, 당연히 mid가 더 커져야 하기에 s를 키워준다.

 

반대로, C와 같거나 작을 경우 길이를 더 줄여야 하기에 e를 줄여준다.

 

 

2. 통나무 자르는 횟수 구하기

    static int getCutCount(List<Long> arr, long mid, int K, int C){
        int cutCnt = 0;    // 자르는 횟수
        long distance = 0; // 구간 길이
        
        for(int i=K; i>=0; i--){ // firstCut을 위해 반대로 자른다.
            distance += (arr.get(i+1) - arr.get(i));
            
            if(distance > mid){ // mid보다 클 경우
                distance = arr.get(i+1) - arr.get(i);
                cutCnt++;
                
                if(distance > mid){ // 현재 구간이 mid보다 큰 경우 -> 불가능
                    cutCnt = C+1; // 불가능한 경우임으로 C+1을 해서 s를 늘려준다.
                    break;
                }
            }
        }

        if(cutCnt < C) firstCut = arr.get(1); // 더 자를 수 있으므로 첫번째 구간을 자른다.
        else firstCut = distance; // 더 자를 수 없기 때문에, 마지막으로 자른 위치를 반환한다.

        return cutCnt;
    }

 

getCutCount 함수는 모든 통나무의 길이가 mid보다 같거나 작게 만드는 횟수를 반환해 준다.

 

뒤에서부터 탐색을 하며 distance(구간) 값을 경신해 준다.

 

만약 mid보다 클 경우 이전까지 구한 구간 값을 제외하고 cutCnt를 늘리고 다시 탐색한다.

 

만약 또 mid보다 큰 경우 하나의 구간이 mid보다 큰 경우이기에 불가능한 경우 처리를 해준다.

 

cutCnt가 C보다 작을 경우 첫 번째 자를 수 있는 구간을 저장하고, 아닐 경우 마지막으로 자른 위치를 저장한다.

 

 

전체 코드(성공) :

import java.io.IOException;
import java.io.*;
import java.util.*;
public class Main {
    static long firstCut;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long L = Long.parseLong(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        List<Long> arr = new ArrayList<>();
        for(int i=0; i<K; i++){
            arr.add(Long.parseLong(st.nextToken()));
        }
        arr.add(0L);
        arr.add(L);
        Collections.sort(arr);

        long s = 1;
        long e = L;
        long ansLongest = L;
        long ansFirst = 0;

        while(s<=e){
            long mid = (s + e) / 2;
            int cutCnt = getCutCount(arr, mid, K, C);

            if(cutCnt <=C){
                ansLongest = Math.min(mid, ansLongest);
                ansFirst = firstCut;
                e = mid-1;
            }
            else{
                s = mid+1;
            }
        }

        System.out.println(ansLongest + " " + ansFirst);
    }

    static int getCutCount(List<Long> arr, long mid, int K, int C){
        int cutCnt = 0;
        long distance = 0;
        for(int i=K; i>=0; i--){
            distance += (arr.get(i+1) - arr.get(i));
            if(distance > mid){
                distance = arr.get(i+1) - arr.get(i);
                cutCnt++;
                if(distance > mid){
                    cutCnt = C+1;
                    break;
                }
            }
        }

        if(cutCnt < C) firstCut = arr.get(1);
        else firstCut = distance;

        return cutCnt;
    }
}

 

이분탐색에 조금 감이 잡혀서 조금만 더 집중하면 풀 수 있었을 것 같은데 아쉬운 것 같다.