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

Minsu Lee·2023년 3월 3일

Java algorithm

baekjoon

목록 보기

13/16

🎆백준 1654번 랜선 자르기🎆

📌문제

🔍문제 설명

문제 링크 : https://www.acmicpc.net/problem/1654

🔍예제 입력

4 11
802
743
457
539

🔍예제 출력

200

📌풀이

🔍풀이 설명

이분 탐색(Binary Search)을 이용한 문제였다.

이분탐색 (Binary Search) : 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

이진 탐색은 정렬된 데이터를 이용해 탐색하는 방법이므로 탐색하고자 하는 리스트, 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

변수 3개(start, end, mid 혹은 min max, mid 등)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

이 문제는 전에 풀이했던 나무 자르기와 유사한 유형이다. 우선 랜선의 길이를 구해야하는 변수로 두고 입력받은 랜선의 길이중 min값과 max값을 이용해 이분탐색을 하여 구하는 방식이다.

길이에서 최대값(max)은 주어진 랜선의 길이중 최대값+1로 설정하고 최소값(min)은 0으로 시작한다.
mid = (min+max)/2로 설정한 후 주어진 랜선의 길이에서 얻어낼 수 있는 랜선의 수 n을 구한다.
n과 N을 비교해 n<N이면 max = mid로 설정해 잘라지는 길이가 더 증가하도록 설정하고 아닌 경우 min = mid+1로 잘라지는 길이가 더 줄어들도록 설정한다.
위의 과정을 min<max인 경우 반복한다.

주의할 점 데이터의 크기(잘랐을 때 구해지는 길이..)가 int의 범위를 넘을 수 있으므로 long으로 설정하고 실행한다.

{upper bound 형식}
mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다. 그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.

🔍코드

package Binary_Search;

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

//랜선 자르기
public class p1654 {
    public static void main(String[] args)throws Exception{
        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 mid=0;
        long min=0;
        int l[] = new int[K];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            l[i] = number;
            if(number>max){
                max = number;
            }
        }
        max++; //+1을 더 해서 시작
        long n;
        while(min<max){
            n=0;
            mid = (min + max) / 2;
            //mid의 랜선의 길이면 필요한 개수 N이 맞는지 검사
            for(int i=0; i<K; i++){
                n += (l[i]/mid);
            }

             /*  [upper bound 형식]
             *
             *  mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면
             *  자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
             *  그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
             */

            if(n<N){ // 랜선 개수가 모자라면 max값을 줄임
                max = mid;
            }
            else{
                min = mid +1;
            }
        }
        System.out.print(min-1);
    }
}