[Algorithm] 99클럽 코테 스터디 2일차 TIL | 백준_랜선 자르기(1654번)

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

 

---

해당 문제는 이분탐색 알고리즘으로 분류된다.

이분탐색(Binary Search)은 데이터를 반씩 줄여가며 탐색하는 알고리즘으로 원하는 값을 빠르게 찾기 위해 사용되는 알고리즘이다.

 

랜선 중 가장 긴 길이를 max라는 변수에 넣고

중간값을 구한다.

 

mid = (low + high) / 2

mid 값으로 랜선을 나누면 랜선 개수가 나오고,

랜선 개수의 합이 N개 보다 크다면 mid 값을 증가시키고, N개 보다 작다면 mid 값을 감소시켜야 한다. 

if(count >= N){
    result = mid;
    low = mid + 1;//랜선의 최대 길이를 찾아야하므로
}else{
    high = mid - 1;
}

 

랜선의 최대 길이를 찾아야하므로 mid값이 증가하는 로직에서 원하는 정답값이 만들어질 것이다.

그러므로 랜선 개수의 합이 N개 일때도 mid 값이 증가해야 한다.

 

전체 풀이는 아래와 같다.

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

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());

        int[] arr = new int[K];

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

        long max = 0;

        for(int num : arr){
            max = Math.max(num, max);
        }

        long low = 1;
        long high = max;
        long result = 0;

        while(low <= high){
            long mid = (low + high) / 2;

            long count = 0;

            for(int i = 0; i < K; i++){
                count += arr[i] / mid;
            }

            if(count >= N){
                result = mid;
                low = mid + 1;//랜선의 최대 길이를 찾아야하므로
            }else{
                high = mid - 1;
            }
        }
        System.out.println(result);
    }
}

여기서 low를 1로 설정한 이유는 

max가 1이고 low값을 0으로 초기화한다면 

mid 값이 0이 나오고 0으로 수를 나누게 되면 런타임 에러가 발생하기 때문이다.