algorithm - 결정 알고리즘 (이분 검색)

결정 알고리즘

---

결정알고리즘은 이분검색을 활용한 값을 찾아내는 알고리즘 방식이다.
만약, 문제에서 요구하는 값이 lt~rt사이에 존재하면 그 문제는 결정알고리즘으로 해결 가능하다.

문제

뮤직비디오(결정 알고리즘)

m개의 DVD로 음악을 담을 수 있는 DVD의 최소용량

public class ex9 {
    public static int solution(int n,int m,int[] arr){
        int answer=0;
        int lt=arr[n-1]; int rt=0;
        for(int i=0; i<n; i++) rt += arr[i];

        while(lt<=rt){
            int mid = (lt+rt)/2;
            if(count(arr,mid)<=m){ //DVD 2개로도 되면, 3개로도 된다는뜻!
                answer=mid;
                rt=mid-1;
            }
            else lt=mid+1;
        }
        return answer;
    }

    public static int count(int[] arr,int mid){
        int cnt=1,sum=0;
        for(int x : arr){
            if(sum+x>mid){
                cnt++;
                sum=x;
            }
            else sum+=x;
        }
        return cnt;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }

        System.out.println(solution(n,m,arr));
    }
}

풀이

이 문제에서 mid는 DVD 한 장의 용량을 뜻한다.
count함수를 이용해서 mid용량을 가질때 사용되는 DVD의 수를 구한다.
이때 DVD의 수가 m보다 적더라도 그 적은 수는 m개로도 구성할수 있다는 뜻이다.
최소 용량을 구해야하기 때문에 정답이되더라고 rt=mid-1를 해줘서 최솟값을 구해봐야한다.

마구간 정하기(결정 알고리즘)

m마리 말을 좌표에 배치할 때의 두 말 사이의 최대거리.

public class ex10 {
    public static int solution(int n,int m,int[] arr) {
        int answer=0;
        int lt=arr[0]; int rt=arr[n-1];
        while(lt<=rt){
            int mid=(lt+rt)/2;
            if(count(arr,mid)>=m){
                answer=mid;
                lt=mid+1;
            }
            else rt=mid-1;
        }
        return answer;
    }

    public static int count(int[] arr,int mid){
        int cnt=1;
        int ep=arr[0];
        for(int i=1; i<arr.length; i++){
            //arr[i]-ep -> 말과 말사이의 거리
            if(arr[i]-ep>=mid){
                cnt++;
                ep=arr[i];
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }

        System.out.println(solution(n,m,arr));
    }
}

풀이

이 문제에서의 mid는 거리를 뜻한다. ep는 전 말의 위치이다.
1.mid=5 일때, ep=1,ep=8이다.
arr[i]-ep>mid 여야 한다. --> 말 2마리 배치 가능. --> 말이 m보다 적으므로 mid값을 줄여야 한다.
2.mid=2 일때, ep=1,ep=4이다.
arr[i]-ep>mid --> 말 3마리 배치 가능. --> 정답으로는 가능하지만 최대거리는아니다. 말사이의 거리는 3이지만, mid값이 2이므로 mid가 3일 때의 경우(최대거리경우) 를 또 해야한다. 그렇기 때문에 lt=mid+1을 해준다.
3.mid=3 일떄, ep=1,ep=4이다.
arr[i]-ep>mid --> 말 3마리 배치 가능. --> 정답!