[백준] 1654번 랜선 자르기 문제 이분탐색 활용해서 풀어보기 : Programming Story

1. 문제

www.acmicpc.net/problem/1654

문제는 위의 링크에 들어가면 볼 수 있다.

2. 풀이

이 문제는 이분탐색을 활용해서 해결할 수 있는 문제이다.

사실 모든 랜선의 길이를 하나씩 다 구해보는 방법도 있겠지만 그러면 시간이 오래걸리기 때문에 이분탐색으로 해서 시간을 줄이는 방법을 사용하면 된다.

처음에 left의 값은 1로 시작하고 right의 값은 랜선 길이 중에서 최대길이로 시작을 한다. ok라는 함수를 만들어서 랜선의 길이가 문제에서 주어진 개수보다 많거나 같으면 true를 return하고 작으면 false를 return한다.

public static boolean ok(long mid){
        int cnt=0;
        for(int i=0; i<a.length;i++){
            cnt+=(a[i]/mid);
        }
        return (cnt>=k);
    }

만약 return 값이 true라면 숫자를 증가시켜도 된다는 뜻이므로 left의 값을 mid+1로 조정하고, false라면 숫자를 낮추어야 한다는 뜻이므로 right를 mid-1로 조정한다.

이를 반영한 이분탐색 부분의 코드는 아래와 같다.

 long ans=0;
        long left=1;
        long right=max;
        while(left<=right){
            long mid=(left+right)/2;
            if (ok(mid)){//원하는 개수 이상으로 만들 수 있음
                left=mid+1;
                ans=Math.max(ans, mid);
            }
            else{
                right=mid-1;
            }
        }

이렇게 이분탐색을 진행하면 빠르게 문제를 해결할 수 있다.

3. 코드

전체 코드는 아래와 같다.

import java.util.*;

public class Main{
    static int k;
    static long a[];
    public static boolean ok(long mid){
        int cnt=0;
        for(int i=0; i<a.length;i++){
            cnt+=(a[i]/mid);
        }
        return (cnt>=k);
    }
        
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
         k=sc.nextInt();
        a=new long[n];
        long max=0; //가장 길이가 긴 랜선 길이 저장
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
            max=Math.max(max, a[i]);
        }
        long ans=0;
        long left=1;
        long right=max;
        while(left<=right){
            long mid=(left+right)/2;
            if (ok(mid)){//원하는 개수 이상으로 만들 수 있음
                left=mid+1;
                ans=Math.max(ans, mid);
            }
            else{
                right=mid-1;
            }
        }
        System.out.println(ans);
        
    }
}