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

문제 바로가기 : https://www.acmicpc.net/problem/1654

메모리 : 17312KB

시간 : 188ms

언어 : Java 11

---

코드

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

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 K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] rope = new int[K];
        for (int i = 0; i < K; i++) {
            rope[i] = Integer.parseInt(br.readLine());
        }
        long left = 0;
        long right = Integer.MAX_VALUE;
        while (left <= right) {
            long mid = (left + right) / 2;
            long cnt = 0;
            for (int i = 0; i < K; i++) {
                cnt += rope[i] / mid;
            }
            if (cnt < N) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(right);
    }

}

풀이

로프의 최대길이를 구하는 문제다. 로프를 잘라서 개수를 맞춰야하는데 최댓값을 구하기 위해 길이를 하나하나 대입해 봐야한다. 하지만 시간초과가 날 것이기 때문에, 이분탐색을 통해 최대길이를 구할 수 있다. 로프의 최대 길이는 2^31 - 1 이므로 int범위 안이라서 right를 Integer.MAX_VALUE로 지정하고 이분탐색을 실행했다. mid가 로프의 값이 되고, 가진 로프를 mid값으로 나눈 cnt가 목표인 N보다 작으면 길이가 짧다는 뜻이므로 left를 mid보다 +1 크게 옮기고 N보다 크면 길다는 뜻이므로 right를 mid - 1 로 옮겨 짧아지게 한다.