[백준/JAVA] 1654번: 랜선 자르기

🔺 문제

1654번: 랜선 자르기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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(), " ");
        
        int K = Integer.parseInt(st.nextToken());   // 이미 갖고 있는 랜선 개수
        int N = Integer.parseInt(st.nextToken());   // 필요한 랜선 개수
        
        long max = 0;
        long min = 0;
        long mid = 0;
        
        long[] A = new long[K];
        for(int i = 0 ; i < K ; i++) {
            A[i] = Long.parseLong(br.readLine());
            if(A[i] > max) max = A[i];
        }
        
 
        /** 🔔 이진 탐색 🔔 **/
        max++;
        while(min < max) {
            mid = (min + max) / 2;
            
            long total = 0;
            for(int i = 0 ; i < K ; i++) {
                total += A[i] / mid;
            }
            
            if(total < N) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
 
        System.out.println(min - 1);    // 최적값 조정
    }
}
 

✅ 해결 아이디어
✔ 이진 탐색
- Line 33 : total이 N보다 작다는 것은, mid 값이 너무 크다는 의미이므로 max 값을 더 작게 조정

 

💥 유의사항

• Line 24 :  반드시  max에서 +1 값이어야 함.

• Line 40 : 마지막에 출력할 때 min이 아닌, min - 1로 해줘야 함.

 

 

---

💬 느낀 점

이진 탐색.. 오랜만이고....

그렇다...

 

 

1회독	2회독	3회독	4회독	5회독
V

 

---

(참고)

[백준] 1654번 : 랜선 자르기 - JAVA [자바]