백준 - 랜선 자르기(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1654

[문제 설명]

전형적인 이분탐색을 이용하는 문제

 

[접근 방법]

딱 봐도 이분탐색이라 자신 있게 접근했다가, 부족함을 알게해준 문제.

https://st-lab.tistory.com/269

[백준] 1654번 : 랜선 자르기 - JAVA [자바]

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

상계 하계 Upper Bound, Lower Bound 이분탐색을 풀기 위해 꼭 필요한 기본적인 개념 같다.

굉장히 정리가 잘 된 블로그가 있어서 도움을 받았다. 예전에 리트코드에서 비슷한 글을 봤다가 휙 지나쳤는데, 꼭 집고 넘어가야 했던 개념같다.

+) 범위 신경 안쓰고 무지성 int 썼다가 초반에 헤멨다. 이것도 반성할 점. 이상하게 꼭 신경 써야하는 문제에서 신경 안쓰게 된다.

아무튼 시간 복잡도는 log랜선의길이*K => 31log2 * 10000 => 9만?정도 될듯하다.

 

시간복잡도 O(K*log랜선길이)

공간복잡도 O(K)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int cntOfLANCable = Integer.parseInt(st.nextToken());
        int cntOfNeededCable = Integer.parseInt(st.nextToken());
        long[] arrOfCables = new long[cntOfLANCable];
        long maxLength = 0;
        for (int i = 1; i <= cntOfLANCable; i++) {
            long temp = Integer.parseInt(br.readLine());
            arrOfCables[i-1] = temp;
            maxLength = Math.max(temp, maxLength);
        }

        long answer = getMaximumCableLength(arrOfCables, cntOfNeededCable, maxLength);
        System.out.println(answer);
    }

    private static long getMaximumCableLength(long[] arrOfCables, int cntOfNeededCable, long maxLength) {
        long left = 1;
        long right = maxLength;

        while (left <= right) {
            long currentLength = left + (right-left)/2;
            int cntOfCurrentCable = 0;
            for (int i = 0; i < arrOfCables.length; i++) {
                cntOfCurrentCable += arrOfCables[i]/currentLength;
            }

            if (cntOfNeededCable > cntOfCurrentCable) {
                right = currentLength-1;
            } else {
                left = currentLength+1;
            }
        }

        return left-1;
    }
}