백준(BOJ) 1654 : 랜선 자르기 (실버2) / 자바(Java) 풀이

문제

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

3줄 요약

1. K개의 랜선과 필요한 랜선의 개수 N을 입력받아, 각 랜선의 길이를 배열 A에 저장합니다. 랜선 길이의 최댓값이 2^31-1일 수 있으므로, s, e, mid를 비롯한 관련 변수들을 long 타입으로 선언하여 오버플로우를 방지합니다.
2. 이분 탐색을 사용하여 랜선을 자를 수 있는 최대 길이를 찾습니다. 중간 길이 mid로 랜선을 잘랐을 때 나오는 랜선의 개수를 long 타입의 result에 누적하여 N과 비교합니다. 이는 upper bound를 찾는 과정으로, 조건을 만족하는 최대 길이를 탐색합니다.
3. 최종적으로 이분 탐색이 종료되었을 때의 끝 길이 e가 최대 랜선 길이가 되며, 이를 출력합니다. Upper bound 탐색 결과로 얻은 e 값은 조건을 만족하는 최대 길이입니다.

코드

// package boj1654;

import java.io.*;
import java.util.stream.Stream;

public class Main {
   public static void main(String[] args) throws Exception {
       // 표준 입력 사용 시 아래 주석 해제
       // System.setIn(new FileInputStream("src/input.txt"));

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       // 첫 번째 줄에서 K와 N 입력받기
       int[] arr = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
       int K = arr[0]; // 가지고 있는 랜선의 개수
       int N = arr[1]; // 필요한 랜선의 개수

       int[] A = new int[K]; // 랜선의 길이를 저장할 배열
       for (int i = 0; i < K; i++) {
           A[i] = Integer.parseInt(br.readLine()); // 랜선의 길이 입력받기
       }

       br.close(); // 입력 스트림 닫기

       long s = 1; // 랜선의 길이는 자연수이므로 1부터 시작
       long e = Integer.MAX_VALUE; // 랜선의 최대 길이로 초기화

       while (s <= e) {
           long mid = (s + e) / 2; // 중간 길이 계산
           long result = 0; // 랜선 개수 합산 변수

           for (int a : A) {
               result += a / mid; // 각 랜선을 중간 길이로 나눈 개수 누적
           }

           if (result >= N) {
               s = mid + 1; // 더 긴 길이 탐색
           } else {
               e = mid - 1; // 더 짧은 길이 탐색
           }
       }

       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       bw.write(Long.toString(e)); // 정답 출력 (최대 랜선 길이)
       bw.flush(); // 출력 버퍼 비우기
       bw.close(); // 출력 스트림 닫기
   }
}