[알고리즘] 2343 블루레이 만들기

🗒️ 문제 : 백준 2343 블루레이 만들기

📎 분류 : binary search

예시)

강의는 총 9개이고, 블루레이는 총 3개 가지고 있다.

1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에, 블루레이의 크기는 17이 된다. 17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.

접근방식

이 문제는 블루레이 하나의 최대 크기를 이진 탐색으로 찾는 문제이다.

• low = 강의 중 가장 긴 강의 시간 (블루레이 최소 크기)
• high = 모든 강의 시간을 합한 값 (블루레이 최대 크기)

이진 탐색을 통해, **블루레이 하나당 최대 크기(mid)**를 정하고, 그 크기(mid)로 모든 강의를 나눴을 때, 블루레이 개수가 조건을 만족하는지 확인한다.

• 만약 블루레이 개수가 조건보다 작거나 같으면 (= mid 크기로 충분히 담을 수 있으면)
  • 더 작은 크기로도 가능할지 확인하기 위해 high를 줄인다.
• 반대로 블루레이 개수가 조건보다 많으면 (= mid 크기로는 너무 많이 나눠져야 하면)
  • 블루레이 크기를 키우기 위해 low를 키운다.

if (count <= m){ //가능한 블루레이 개수인지
    high = mid-1;
}else{//count > m
    low = mid+1;
 }

 

코드

package 알고리즘_코딩테스트.dayone.mar03;

import java.io.*;
import java.util.*;

/**
 9 3
 1 2 3 4 5 6 7 8 9
 */
public class BOJ_2343 {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static int n,m;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n];
        int maxsum, minsum = 0;
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] > minsum)
                minsum = arr[i];
        }

        // 레슨 시간 이진탐색 범위 구하기
        maxsum = Arrays.stream(arr).sum();

        int low = minsum;
        int high = maxsum;

        while(low <= high){
            int mid = (high + low) / 2; //블루레이 크기 후보
            int sum = 0; //레슨합
            int count = 0; //필요한 블루레이 개수
            for (int i = 0 ; i < n; i++){
                if (sum + arr[i] > mid){
                    count++;//하나의 블루레이 추가
                    sum = 0;
                }
                sum = sum + arr[i];
            }
            if (sum != 0){
                count++;
            }
            if (count <= m){ //가능한 블루레이 개수인지
                high = mid-1;
            }else{//count > m
                low = mid+1;
            }
        }

        System.out.println(low);
    }
}