[백준] 2343번 - 기타 레슨 (Java)

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

<문제 해석>

1. 강의 순서가 바뀌면 안된다는 것은 입력 받은 순서대로 디스크에 배치되어야 한다는 것이다.

2. 최소 디스크의 갯수는 M개로 정해져있다. 한 디스크의 최소 용량을 구해야 한다.

 

<풀이>

1) 완전탐색(DFS) 

완전탐색으로 각 디스크에 곡들을 저장해서 그 중 최소값을 구하자.

각 디스크에 저장하는 곡의 수는 for문으로 정해야 하나? DFS로 구현을 하면 어떻게 할 수 있을까?

각 디스크에 저장하는 곡의 수가 랜덤하다. 그래서 DFS의 종료조건을 정할 수가 없다.

저장곡수가 정해져 있다면 몇 곡 이상이 되면 return을 할 수가 있을텐데...

 

전체 곡 시간을 구해서 M으로 나누면 각 디스크에 저장할 수 있는 평균 시간을 구할 수가 있는데 이걸 기준으로 삼아보는건 어떨까? 하지만, 평균보다 높다고 리턴을 해버리면 결과값이 틀어질 수가 있다.

 

2) 이분탐색

이분탐색 알고리즘을 사용하려면 start, end, mid, target을 어떤 항목으로 할 것인지가 명확해야 한다.

그런데, 이 문제는 어떤 항목을 어떻게 적용해야 할지가 선명하게 떠오르지가 않았다.

 

먼저 주어진 항목들을 나열해보았다.

  - 오름차순으로 정렬된 강의 시간들 : N개 만큼의 숫자들

  - 블루레이 디스크 갯수 : M

 

target : 디스크 한장에 담을 수 있는 강의 시간

start(최소) : 강의는 중간에 끊기면 안되기 때문에 무조건 가장 강의시간이 긴 강의도 한장의 디스크에 담겨야 한다.

end(최대) : 전체 강의 시간의 총합

 

가능한 크기 중의 최소를 구하여야 하기 때문에 target을 포함하는 LowerBound로 구현하자.

mid값을 변경해 가면서 M장을 사용하는 디스크 당 용량 중에 최소용량을 구하자.

 

<LowerBound 구현>

1. start와 end값을 정하고, mid 값을 구해서 범위를 비교하는 함수를 이분탐색으로 먼저 구한다.

       int lowerBound = 0;
        while (start <= end) {
            mid = (start + end)/2;
            // 디스크 용량이 mid일 때 M장에 다 담을 수 있는지 계산
            //System.out.println("min= "+min+", max= "+max+", mid= "+mid);
            int sum = 0;
            int count = 1;
            for (int i=0; i<N; i++) {
                // sum과 지금 강의를 합치면 디스크 1장을 넘어갈 때 장수를 추가한다.
                if (sum + A[i] > mid) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }
            // 디스크 한장 용량의 최소값을 구해야 한다.
            // 디스크 장수가 M만큼 나오는 mid가 나왔을 때 더 적은 mid값이 있을 수 있기 때문에 상한값을 내려야 한다.
            if (count < M) { // 장수가 M보다 작다는 것은 장당 용량의 크기를 줄여야 한다는 뜻이다. 상한값을 내리자.
                end = mid - 1;
            } else if (count == M) { // 장수가 M과 일치한다. 
                lowerBound = mid;            
            } else { // 장수가 M보다 크다는 것은 장당 용량의 크기를 늘여야 한다는 뜻이다. 하한값을 올리자.
                start = mid + 1;
            }            
        }
        return lowerBound;

 

2. LowerBound 형태로 수정한다.

디스크 장수가 M가 일치하는 디스크 용량이 여러개가 있을 수 있다. 그 중 가장 최소값을 찾아야 한다.

그렇다면 상한값을 줄여나가야지 최소값을 구할 수가 있다. (end = mid -1)

if (count < M)도 상한값을 내려야 하고, if (count == M)도 상한값을 내려야 하기 때문에 두 식을 합친다.

        int lowerBound = 0;
        while (start <= end) {
            mid = (start + end)/2;
            // 디스크 용량이 mid일 때 M장에 다 담을 수 있는지 계산
            //System.out.println("min= "+min+", max= "+max+", mid= "+mid);
            int sum = 0;
            int count = 1;
            for (int i=0; i<N; i++) {
                // sum과 지금 강의를 합치면 디스크 1장을 넘어갈 때 장수를 추가한다.
                if (sum + A[i] > mid) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }
            // 디스크 한장 용량이 값들 중에서 최소값을 구해야 한다.
            // 디스크 장수가 M만큼 나오는 mid가 나왔을 때 더 적은 mid값이 있을 수 있기 때문에 상한값을 내려야 한다.
            if (count <= M) { // 장수가 M보다 작다는 것은 장당 용량의 크기를 줄여야 한다는 뜻이다. 상한값을 내리자.
                lowerBound = mid;
                end = mid - 1;
            } else { // 장수가 M보다 크다는 것은 장당 용량의 크기를 늘여야 한다는 뜻이다. 하한값을 올리자.
                start = mid + 1;
            }            
        }
        return lowerBound;

 

<전체코드>

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

public class Main {
    static int N, M;
    static int A[];

 
    void inputData(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }
        sc.close();
    }

    void Solve() {
        int start = 0, end = 0, mid = 0;

        // start와 end값을 구한다.
        for (int x : A) {
            end += x;
            start = Math.max(start, x);
        }

        int lowerBound = 0;
        while (start <= end) {
            mid = (start + end)/2;
            // 디스크 용량이 mid일 때 M장에 다 담을 수 있는지 계산
            //System.out.println("min= "+min+", max= "+max+", mid= "+mid);
            int sum = 0;
            int count = 1;
            for (int i=0; i<N; i++) {
                // sum과 지금 강의를 합치면 디스크 1장을 넘어갈 때 장수를 추가한다.
                if (sum + A[i] > mid) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }
            // 디스크 한장 용량의 최소값을 구해야 한다.
            // 디스크 장수가 M만큼 나오는 mid가 나왔을 때 더 적은 mid값이 있을 수 있기 때문에 상한값을 내려야 한다.
            if (count <= M) { // 장수가 M보다 작다는 것은 장당 용량의 크기를 줄여야 한다는 뜻이다. 상한값을 내리자.
                lowerBound = mid;
                end = mid - 1;
            } else { // 장수가 M보다 크다는 것은 장당 용량의 크기를 늘여야 한다는 뜻이다. 하한값을 올리자.
                start = mid + 1;
            }            
        }
        System.out.println(lowerBound);

    }
 
    public static void main(String[] args) {
        Main m = new Main();
        m.inputData(); // 입력함수
        m.Solve();
    }
}

 

<제출 결과>