[2343] 기타 레슨

✔ 기타 레슨

[백준 2343]

문제 분석하기

블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 하므로

블루레이에 첫 레슨부터 마지막 레슨까지 차례대로 저장하면서 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단

만약 모두 저장할 수 있다면 블루레이 크기를 줄이고, 저장할 수 없다면 블루레이 크기를 늘리도록 함

손으로 풀어보기

1. 시작 인덱스를 최대 길이의 레슨으로, 종료 인덱스를 모든 레슨 길이의 합으로 이진 탐색
   • 시작 인덱스 > 종료 인덱스일 때까지 수행
   • 중앙값 크기로 모든 레슨을 저장할 수 있으면 종료 인덱스 = 중앙값 - 1
   • 중앙값 크기로 모든 레슨을 저장할 수 없다면 시작 인덱스 = 중앙값 + 1

예) 레슨 수 : 9 (1, 2, 3, 4, 5, 6, 7, 8, 9), 블루레이 수 : 3

탐색 번호	중앙값	몇 장의 블루레이	인덱스 수정	종료 조건 만족
1	(9 + 45) / 2 = 27	(1 + 2 + 3 + 4 + 5 + 6) / (7 + 8 + 9) 2장	블루레이 3장으로 저장 가능 종료 인덱스 = 27 - 1 = 26	x
2	(9 + 26) / 2 = 17	(1 + 2 + 3 + 4 + 5) / (6 + 7) / (8 + 9) 3장	블루레이 3장으로 저장 가능 종료 인덱스 = 17 - 1 = 16	x
3	(9 + 16) / 2 = 12	(1 + 2 + 3 + 4) / (5 + 6) / (7) / (8) / (9) 5장	블루레이 3장으로 저장 불가능 시작 인덱스 = 12 + 1 = 13	x
4	(13 + 16) / 2 = 14	(1 + 2 + 3 + 4) / (5 + 6) / (7) / (8) / (9) 5장	블루레이 3장으로 저장 불가능 시작 인덱스 = 14 + 1 = 15	x
5	(15 + 16) / 2 = 15	(1 + 2 + 3 + 4 + 5) / (6 + 7) / (8) / (9) 4장	블루레이 3장으로 저장 불가능 시작 인덱스 = 15 + 1 = 16	x
6	(16 + 16) / 2 = 16	(1 + 2 + 3 + 4 + 5) / (6 + 7) / (8) / (9) 4장	블루레이 3장으로 저장 불가능 시작 인덱스 = 16 + 1 = 17	start > end 17 > 16 o
탐색 종료 후 start 값인 17이 블루레이 크기의 최솟값

슈도코드 작성하기

N(레슨 개수) M(블루레이 개수)
A(기타 레슨 데이터 저장 배열)
start(이진 탐색 시작 인덱스)
end(이진 탐색 종료 인덱스)
for(N의 개수만큼 반복하기) {
    A 배열 저장하기
    시작 인덱스 저장(A 배열 중 최솟값)
    종료 인덱스 저장(A 배열의 총합)
}
while(시작 인덱스 <= 종료 인덱스) {
    middle(중간 인덱스)
    sum(레슨 합)
    count(현재 사용한 블루레이 개수)
    for(N의 개수만큼 반복하기) {
        만약 sum + 현재 레슨 시간 > 중간 인덱스이면
        count 값을 올리고 sum을 0으로 리셋하기
        sum에 현재 레슨 시간값 더하기
    }
    sum이 0이 아니면 마지막 블루레이가 필요하므로 count값 올리기
    if(count > M: 중간 인덱스 값으로 모든 레슨 저장 불가능)
        시작 인덱스 = 중앙 인덱스 + 1
    else(중앙 인덱스값으로 모든 레슨 저장 가능) 
        종료 인덱스 = 중앙 인덱스 - 1
}
시작 인덱스 출력하기

코드 구현하기

/**
 * 2343) 기타_레슨
 */
public class D030_2343 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(레슨 개수)
        int N = sc.nextInt();
        // M(블루레이 개수)
        int M = sc.nextInt();
        // A(기타 레슨 데이터 저장 배열)
        int[] A = new int[N];
        // start(이진 탐색 시작 인덱스)
        int start = 0;
        // end(이진 탐색 종료 인덱스)
        int end = 0;
        for (int i = 0; i < N; i++) {
            // A 배열 저장하기
            A[i] = sc.nextInt();
            // 시작 인덱스 저장(A 배열 중 최솟값)
            if (start < A[i])
                start = A[i];
            // 종료 인덱스 저장(A 배열의 총합)
            end = end + A[i];
        }
        while (start <= end) {
            // middle(중간 인덱스)
            int middle = (start + end) / 2;
            // sum(레슨 합)
            int sum = 0;
            // count(현재 사용한 블루레이 개수)
            int count = 0;
            for (int i = 0; i < N; i++) {
                // 만약 sum + 현재 레슨 시간 > 중간 인덱스이면
                if (sum + A[i] > middle) {
                    // count 값을 올리고 sum을 0으로 리셋하기 (다음 블루레이에 저장하기 위해서)
                    count++;
                    sum = 0;
                }
                // sum에 현재 레슨 시간값 더하기
                sum = sum + A[i];
            }
            // sum이 0이 아니면 마지막 블루레이가 필요하므로 count값 올리기
            if (sum != 0)
                count++;
            // 중간 인덱스 값으로 모든 레슨 저장 불가능
            if (count > M)
                start = middle + 1;
            // 중앙 인덱스값으로 모든 레슨 저장 가능
            else
                end = middle - 1;
        }
        // 시작 인덱스 출력하기
        System.out.println(start);
    }
}