[코딩테스트] 백준 2343 자바

백준 2343

백준 2343 문제

해당 문제는 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 하므로 문제 조건이 이진 탐색 알고리즘을 선택하는 것이 좋다.

블루레이에 첫 레슨부터 미자막 레슨까지 차례대로 저장하다 보면 저장한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다.

모두 저장할 수 있다면 블루레이 크기를 줄이고 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 블루레이 크기의 최솟값을 알 수 있다.

이진 탐색의 시작 인덱스는 최대 길이의 레슨이고 종료 인덱스는 모든 레슨 길이의 합이다.

예시를 보면, 총 9개로 구성된 레슨의 시간은 각각 1, 2, 3, 4, 5, 6, 7, 8, 9이므로 이진 탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다. 블루레이 개수가 3일 때 9~45 사이에서 블루레이 크기의 최솟값을 이진 탐색으로 찾으면 된다.

import java.util.*;

public class Boj2343 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 레슨 개수
        int m = sc.nextInt(); // 블루레이 개수
        int[] arr = new int[n]; // 기타 레슨 데이터 저장 배열
        int start = 0; // 이진 탐색 시작 인덱스
        int end = 0; // 이진 탐색 종료 인덱스

        for (int i = 0; i < n; i++) { // n의 개수만큼 반복
            arr[i] = sc.nextInt(); // arr 배열 저장
            if (start < arr[i]) {
                start = arr[i]; // 레슨 최댓값을 시작 인덱스로 저장
            }
            end += arr[i]; // 모든 레슨의 총합을 종료 인덱스로 저장
        }

        while (start <= end) {
            int mid = (start + end) / 2; // 중간 인덱스
            int sum = 0; // 레슨 합
            int count = 0; // 현재 사용한 블루레이 개수

            for (int i = 0; i < n; i++) { // n의 개수만큼 반복하며 mid값으로 모든 레슨을 저장할 수 있는지 확인
                if (sum + arr[i] > mid) { // 만약 sum + 현재 레슨 시간 > 중간 인덱스이면
                    count++; // count값을 올리고
                    sum = 0; // sum을 0으로 리셋
                } // 현재 블루레이에 저장할 수 없어 새로운 블루레이로 교체한다는 의미

                sum += arr[i]; // sum에 현재 레슨 시간값 더하기
            }

            if (sum != 0) { // sum이 0이 아니면 블루레이가 1개 더 필요하므로 더함
                count++; // count값 올리기
            }

            if (count > m) { // count가 m보다 크면 중간 인덱스 값으로 모든 레슨 저장 불가능
                start = mid + 1; // 시작 인덱스 = 중간 인덱스 + 1
            } else { // 중간 인덱스 값으로 모든 레슨 저장 가능
                end = mid - 1; // 종료 인덱스 = 중앙 인덱스 - 1
            }
        }

        System.out.println(start); // 시작 인덱스 출력
    }
}

문제 풀이

1. 레슨 개수를 n에 저장한다.
2. 블레루이 개수를 m에 저장한다.
3. 기타 레슨 데이터 저장 배열 arr를 선언한다.
4. 이진 탐색 시작 인덱스 start를 0으로 초기화한다.
5. 이진 탐색 종료 인덱스 end를 0으로 초기화한다.
6. n의 개수만큼 반복하면서 arr에 기타 레슨 데이터를 저장하고, 레슨 최대 길이를 start에 업데이트를 해주고, 모든 레슨 길이를 end에 더해준다.
7. start가 end보다 커지기 전까지 반복한다.
8. 중간 인덱스 mid를 구해서 저장한다.
9. 레슨 합 sum을 0으로 초기화한다.
10. 현재 사용한 블루레이 개수 count를 0으로 초기화한다.
11. n의 개수만큼 반복하며 mid값으로 모든 레슨을 저장할 수 있는지 확인한다.
12. 만약 sum + 현재 레슨 시간(arr[i])가 중간 인덱스(mid)보다 크다면 count값을 올리고, sum을 0으로 리셋한다.
13. sum에 현재 레슨 시간값(arr[i])를 더한다.
14. sum이 0이 아니면 블루레이가 1개가 더 필요하므로 count를 하나 올린다.
15. count가 m보다 크면 중간 인덱스값(mid)으로 모든 레슨을 저장하지 못하기 때문에 start를 mid + 1로 바꾼다.
16. 반대로 count가 m보다 작거나 같으면 중간 인덱스 값으로 모든 레슨을 저장힐 수 있기 때문에 최소 크기를 구하기 위해 end를 mid - 1로 바꾼다.
17. start가 end보다 크거나 같아질 때까지 위의 과정을 반복하다가 start가 end보다 크거나 같아지면 start를 출력한다.