[결정알고리즘] 9. 뮤직비디오

<<풀이>>

 

처음 이 문제를 접근할 때 내 생각대로 진행하려고 했으나 쉽지가 않았다. 

 

그래서 이래저래 해보다가 강사님의 방식을 보니 '이분 검색'을 응용해서 푸셨다.

 

이분 검색은 정렬되어 있는 데이터에 정답이 무조건 있을 때 할 수 있는 알고리즘이다.

 

이 문제도 그렇게 해서 접근할 수 있었는데, 

 

9 3
1 2 3 4 5 6 7 8 9

 

예시를 가져온다면,

 

1 ~ 9 까지의 연속된 합에서 3개로 묶으되 3개의 연속된 값이 가장 작은 경우를 구하는 것이다.

 

그렇다면 이는  9 ~ 45로 둘 수 있다. 이를 각각 lt = 9 rt = 45로 둔다.

 

그렇게 한 뒤에 이분 검색 방식으로 mid를 구한 뒤에, 그 mid 를 가지고 mid와 함께 원래 배열  1 ~ 9를 최소 몇개로 나눠지는지 반환하는 함수에 넣는다. 그렇게 나온 값을 받아 그 값이 3의 크기보다 같거나 아래이면 일단 정답의 후보가 되고,  mid값보다 큰 값은 전부다 가능한 것이기 때문에 신경 쓸 필요가 없다. 그러기에 배제하고 mid 보다 아래쪽을 검색하는데 이때 rt = mid - 1; 로 이동해준다. 그 다음 또 mid를 구해주고 위와 같은 방식을 진행한다.

 

lt > rt가 되기 전까지 반복해서 최종 정답을 도출하는 것이다.

import java.util.Arrays;
import java.util.Scanner;

class Main {

    private int count(int[] arr,int capacity) {
      int cnt = 1, sum = 0;
      for(int x : arr) {
          if(sum + x > capacity) {
              cnt++;
              sum = x;
          } else sum += x;
      }
      return cnt;
    }
    private int solution(int n, int m, int[] arr) {
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).sum();

        while(lt <= rt) {
            int mid = (lt + rt) / 2;
            if(count(arr, mid) <= m) {
                answer = mid;
                rt = mid - 1;
            } else {
                lt = mid + 1;
            }
        }
        return answer;
    }

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

 

 

두 번의 이중 검색을 이용했는데, 좋은 알고리즘 같다 !! 정렬 나오고 그 사이에 값이 무조건 있는 조건에서 특정 값을 찾아낸다면 이 이중 검색 방법을 잊지않고 사용해봐야겠다!!

 

*메서드 안에 메서드를 이용하는 방식을 구현하는 아이디어도 아직까지는 완벽하지 않지만 꾸준히 이용해서 내 것으로 만들자

 

<<추가 공부>>

Arrays 클래스의 stream 메서드 사용

 

 int lt = Arrays.stream(arr).max().getAsInt();
 int rt = Arrays.stream(arr).sum();

 

 

이 방식을 사용했는데 이를 통해 for문을 사용하지 않고 최댓값을 찾고 전체 합을 구할 수 있다!!

 

이것에 대해 따로 정리해놔야겠다.