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

[문제 링크]

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

[난이도]

- Silver 2

 

[알고리즘]

- 파라메트릭 서치

 

[코드]

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

public class Main {
    static int K, N;
    static long left = 1, right = Integer.MIN_VALUE;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new int[K];

        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            right = Math.max(right, arr[i]);
        }

        parametricSearch();

        br.close();
    }
    static void parametricSearch() {
        while (left <= right) {
            long mid = (left + right) / 2;
            long LAN = 0;
            for (int i = 0; i < arr.length; i++) {
                LAN += (arr[i] / mid);
            }
            if (LAN>=N){
                left = mid + 1;
            } else if (LAN < N) {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

- left, right, mid 를 long으로 설정해주어야 한다.

- left의 최소값이 1이어야 한다. 그렇지 않으면 divide by zero 오류가 발생한다. 예를들어 모든 가지고있는 랜선의 길이가 1이고 left가 0일 경우 mid가 0이 된다.