[인프런 알고리즘] Chapter 6, 9번 문제(뮤직비디오- 결정알고리즘)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

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

public class sec06_09 {
    public static int count(int[] arr, int mid)
    {
        int count = 1;
        int sum = 0;
        for(int i = 0; i < arr.length; ++i)
        {
            if(sum + arr[i] > mid)
            {
                ++count;
                sum = arr[i];
            }
            else sum += arr[i];
        }
        return count;
    }

    public static int solution(int[] arr, int N, int M)
    {
        int lPtr = Arrays.stream(arr).max().getAsInt();  // 배열의 최대값
        int rPtr = Arrays.stream(arr).sum();  // 배열의 총합
        int answer = 0;

        while(lPtr <= rPtr)
        {
            int mid = (lPtr + rPtr) / 2;
            if(count(arr, mid) <= M)
            {
                answer = mid;  // 가능한 답을 저장하고, 더 작은 값으로 탐색
                rPtr = mid - 1;
            }
            else lPtr = mid + 1;  // 중간값이 작아서 구간 수가 M보다 많다면, 더 큰 값 탐색
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr, N , M));
    }
}

 

설명

• count 메서드는 주어진 배열을 특정 값(mid)보다 큰 구간 합이 없도록 나누었을 때, 몇 개의 구간이 필요한지 계산하는 역할을 한다. 배열을 순차적으로 더해 가다가 구간 합이 mid를 넘으면 새로운 구간을 시작하고, 구간의 수를 하나 증가시킨다.
  
  
• solution 메서드는 이진 탐색을 사용하여 구간의 최대 합이 최소가 되도록 mid 값을 조정하는 역할을 한다. mid 값을 배열의 최대값과 총합 사이에서 탐색하며, count 메서드로 구간의 수를 계산해가면서 적절한 mid 값을 찾아낸다.