백준 1654번 : 랜선 자르기 자바

 

🧫 문제 분석

✔️ 출처

랜선 자르 실버 2

 

📖 문제

 

이진 탐색, 바이너리 서치

 

이진 탐색에 대해서 공부한 뒤에 풀 수 있었다. 

힙, 트리 자료구조 배웠을 때 배웠었는데 막상 이런거에 적용할 수 있다는 거에서 당황..

 

문제에서 중요한 점

N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

 

그외에는

단순히 이진 탐색을 하면 된다.

1. 중앙 값으로 각 랜선을 나눠서 나온 개수를 구한다.
2. 개수가 n보다 크거나 같으면 최댓값을 구하기 위해 랜선의 길이를 더 늘리고 탐색한다. 
3. 개수가 n보다 적다면 이는 랜선의 길이가 너무 길기 때문에 랜선의 길이를 줄이고 탐색한다. 

 

 

 

---

🔅 문제 풀이

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

public class Main {

    static long[] lanCables;
    static long maxCableLen = 0;
    static int n;
 
    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());
        n = Integer.parseInt(st.nextToken());
        lanCables = new long[k];

		// 랜선 길이 배열에 초기화
        for (int i = 0; i < k; i++) {
            lanCables[i] = Integer.parseInt(br.readLine());
        }

        binarySearch(1, Integer.MAX_VALUE);

        bw.write(maxCableLen + "");
        bw.flush();
        bw.close();
    }

    private static void binarySearch(long left, long right) {

        if (left <= right) {
            long count = 0;
            long mid = (left + right) / 2;
            
            for (int i = 0; i < lanCables.length; i++) {
                count += (lanCables[i] / mid);
            }

	    // 나눈 랜선이 n개 이상이면 최댓값 랜선을 찾기위해 오른쪽 부분 탐색
            if (count >= n) {
                maxCableLen = Math.max(maxCableLen, mid);
                binarySearch(mid + 1, right);
                
            // 나눈 랜선이 n개 미만이면 랜선의 길이를 줄이기 위해 왼쪽 부분 탐색
            } else {
                binarySearch(left, mid - 1);
            }
        }
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  문제 잘 읽기
2. 개념 공부 잘 해놓기