[백준 1654] 랜선 자르기 (JAVA)

백준 1654번 문제 - 랜선 자르기

1654번: 랜선 자르기

---

문제 분석

 

 

 

• K개의 서로 다른 길이의 랜선을 가지고 N개의 동일한 길이의 랜선을 제작하고자 한다.
• 이때 가장 N개의 랜선을 만들 수 있는 가장 긴 길이를 출력해라.

---

해결 키 포인트

 

• K개의 랜선 길이 합을 구하고, 합을 N으로 나눴을 때 값을 알아낸다 : 할 수 있는 최대 랜선 길이 (max)
• 방법 1 : 1부터 max까지 11개를 만들 수 있는 최대 길이 구하기 
  • 실패 ! 시간 초과
• 방법 2 :  이진탐색으로 1부터 max까지 11개를 만들 수 있는 최대 길이 구하기
  • 성공 ! 
  • mid구하는 법 : (low+high) / 2
• • low 값을 0으로 하면 컴파일 오류 발생하므로 low를 1로 설정

---

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] nums = new int[K];
        long sum = 0;
        for (int i = 0; i < K; i++) {
            nums[i] = Integer.parseInt(br.readLine());
            sum += nums[i];
        }

        long result = 0;

        long low = 1, high = sum / N;
        while(low <= high) {
            long mid = (high + low) / 2;
            int count = 0;
            for (int j = 0; j < K; j++) {
                count += nums[j] / mid;
            }
            if (count >= N) {
                result = Math.max(result, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}