[Python/Java] 백준 1654 - 랜선 자르기 [이진 탐색]

 

문제

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

 

해설

이진 탐색을 사용하여 푸는 문제이다. 이진 탐색은 시간복잡도가 \(O(\log n)\)이다

 

Python

from sys import stdin


def solution(lst, n):
    start = 1
    end = max(lst)
    while start <= end:
        cable_num = 0
        mid = (start + end) // 2

        for c in lst:
            cable_num += c // mid

        if n <= cable_num:
            start = mid + 1
        else:
            end = mid - 1
    print(end)


k, n = map(int, stdin.readline().split(" "))
cables = [int(stdin.readline()) for _ in range(k)]
solution(cables, n)

 

Java

1차 시도(실패)

처음 구현한 코드는 아래와 같다. 하지만 Integer overflow 때문인지 오답처리되어 수정이 필요하였다.

 

import java.io.*;
import java.util.*;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int k = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        List<Integer> cables = new ArrayList<>();
        for(int i=0; i<k; i++){
            cables.add(Integer.parseInt(br.readLine()));
        }

        System.out.print(binSearch(cables, n));
    }

    public static int binSearch(List<Integer> cables, Integer n) {
        int start = 1;
        int end = Collections.max(cables);
        
        while(start <= end){
            int cableNum = 0;
            int mid = (start + end) / 2;

            for(int length : cables){
                cableNum += length / mid;
            }

            if(n <= cableNum){
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return end;
    }
}

 

2차 시도(성공)

Integer 부분을 Long으로 바꾸어 처리하였다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().trim().split(" ");
        int k = Integer.parseInt(input[0]);
        long n = Long.parseLong(input[1]);

        List<Long> cables = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            cables.add(Long.parseLong(br.readLine()));
        }

        System.out.print(binSearch(cables, n));
    }

    public static long binSearch(List<Long> cables, long n) {
        long start = 1;
        long end = Collections.max(cables);

        while (start <= end) {
            long cableNum = 0;
            long mid = (start + end) / 2;

            for (long length : cables) {
                cableNum += length / mid;
            }

            if (n <= cableNum) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return end;
    }
}