[백준] 1654 랜선 자르기 - Java

문제

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

 

---

 

문제 개요

오영식은 K개의 서로 다른 길이의 랜선을 가지고 있으며, 이를 잘라 N개의 동일한 길이의 랜선으로 만들어야 합니다. 랜선을 자를 때는 남은 조각을 사용할 수 없고, 자르는 길이는 항상 정수 단위로 진행됩니다. 목표는 N개의 랜선을 만들 수 있는 최대 길이를 구하는 것입니다.

 

접근 방법 

이 문제는 가능한 최대 길이를 찾기 위해 이진 탐색을 사용하는 방법으로 접근할 수 있습니다.

1. 랜선을 만들 수 있는 최소 길이 min = 1과 최대 길이 max = 가장 긴 랜선의 길이를 설정하고, 이진 탐색으로 길이를 탐색합니다.
2. mid를 현재 중간 길이로 설정한 후, 모든 랜선을 mid 길이로 자를 때 총 몇 개의 랜선을 만들 수 있는지 계산합니다.
3. 만들어진 랜선의 개수가 N보다 작다면, mid를 줄여야 하므로 max를 줄이고, 충분히 많은 랜선을 만들 수 있다면 길이를 더 길게 설정해 min을 올려 최대 길이를 찾아나갑니다.

해결 과정

1. 초기 설정
   • min을 1, max를 입력된 랜선 중 최대 길이로 초기화합니다.
2. 이진 탐색 진행
   • min이 max보다 작거나 같을 동안 반복합니다.
   • 각 반복에서 mid를 (min + max) / 2로 설정하고, mid 길이로 각 랜선을 나누어 얻을 수 있는 총 랜선의 개수를 계산합니다.
3. 조건에 따른 길이 조정
   • N개 이상의 랜선을 만들 수 있다면 min을 mid + 1로 설정해 더 긴 길이를 탐색하며, 만들 수 없다면 max를 mid - 1로 줄여 탐색을 이어갑니다.
4. 최대 길이 출력
   • 반복이 끝나면 현재의 max 값이 N개의 랜선을 만들 수 있는 최대 길이입니다.

주요 포인트

1. 이진 탐색을 통한 효율성
   • 길이의 범위를 절반씩 줄이며 탐색하기 때문에 O(log(max) * K)의 시간 복잡도로 효율적입니다.
2. 랜선 개수 계산
   • 각 mid 길이에서 가능한 랜선 개수를 정확하게 계산하여 N개 이상의 랜선을 만들 수 있는지 여부를 확인하는 부분이 중요합니다.
3. long 타입의 사용
   • 주어진 조건에 따라 랜선의 길이는 231−12^{31}-1231−1보다 작거나 같은 자연수입니다. 따라서 길이를 다룰 때는 int 타입의 범위를 초과할 수 있으므로, long 타입을 사용하여 오버플로를 방지해야 합니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long answer = -1;
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[K];

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

        long min = 0;
        while (max >= min) {
            long mid = (max + min) / 2;
            int cnt = 0;
            for(int i=0; i<arr.length; i++) {
                cnt += arr[i] / mid;
            }
            if(cnt < N) {
                max = mid - 1;
            }
            if(cnt >= N) {
                answer = Math.max(answer, mid);
                min = mid + 1;
            }
        }

        System.out.println(answer);
    }
}