[백준] 1654번: 랜선 자르기 (Java)

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

📌 문제 탐색하기

입력 : 첫째 줄 - 기존 랜선의 개수와 K 필요한 랜선의 개수 N (1 ≤ K ≤ 10,000, 1 ≤ n ≤ 1,000,000, K ≤ N)
K줄 - 기존 랜선의 길이 (랜선의 길이 ≤ 2^31-1)
출력 : N개를 만들 수 있는 랜선의 최대 길이

가능한 시간복잡도

O(N log N)

알고리즘 선택

이진 탐색

📌 코드 설계하기

1. K, N, cables (각 랜선 길이를 저장하는 배열)을 input으로 받는다.
2. left는 최소 랜선 길이인 1, right는 최대 랜선의 길이로 초기화한다.
3. 각 랜선을 mid로 잘랐을 때 얻을 수 있는 랜선의 개수를 계산한다.
4. 만약 mid 길이로 N개 이상의 랜선을 만들 수 있으면 더 긴 길이인 mid + 1를 시도하고, 아니라면 더 짧은 길이인 mid - 1을 시도한다.
5. left가 right보다 작거나 같을때까지 반복한 후 최대 길이를 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int K = sc.nextInt();
        int N = sc.nextInt();
        
        int[] cables = new int[K];
        long max = 0;

        for (int i = 0; i < K; i++) {
            cables[i] = sc.nextInt();
            if (cables[i] > max) {
                max = cables[i];
            }
        }
        
        // 이진 탐색
        long left = 1;
        long right = max;
        long mid;
        long result = 0;

        while (left <= right) {
            mid = (left + right) / 2;
            long count = 0;

            for (int cable : cables) {
                count += cable / mid;
            }

            if (count >= N) {
                result = mid; 
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        System.out.println(result);
    }
}