1654번 : 랜선 자르기

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

1654번: 랜선 자르기

 

 

문제

 

 

코드

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int k = Integer.parseInt(st.nextToken()); //갖고 있는 랜선의 수
        int n = Integer.parseInt(st.nextToken()); //필요한 랜선의 수

        int ran[] = new int[k];
        //랜선 입력받기
        for(int i=0;i<k;i++) ran[i] = Integer.parseInt(br.readLine());

        long result=0;
        long start=0;
        long end = Arrays.stream(ran).max().getAsInt();
        //이진탐색 기준: 랜선의 수, 이진탐색의 범위: 랜선의 길이
        while(start<=end) {
            long mid = (start+end)/2; //랜선 길이
            if(mid==0) mid=1;
            
            long count=0;
            for(int i=0;i<k;i++) {
                count+=ran[i]/mid;
            }
            //랜선의 수가 부족하다면 랜선의 길이 줄이기
            if(count<n) end=mid-1;
            //랜선의 수가 충분하다면 랜선의 길이 최대한 늘려보기
            else {
                result = mid;
                start=mid+1;
            }
        }
        System.out.println(result);
    }
}

 

 

해결방법

처음 코드를 구현할 때 랜선의 수를 기준으로 이진 탐색을 수행하였다. 테스트 케이스는 통과했지만 제출해보니 "틀렸습니다."다 떴다. 이유는 범위가 int형의 범위를 초과할 수 있으므로 long형으로 수정해줘야 했다. 수정하여 제출했는데 또 "런타임 에러(ArithmeticException)"가 떴다. 이유는 start:0, end:1 일 경우 mid값이 0이되어 랜선의 수를 구할 때 값을 0으로 나누는 계산을 하기에 예외가 발생하는 것이다. 이를 해결하기위해 if(mid==0) mid=1; 을 추가적으로 작성하였다.