알고리즘 챌린지 3일차

문제

문제: 백준 알고리즘 2343번 기타 레슨

풀이

• 먼저 레슨들을 배열에 저장합니다. 이때 start는 레슨들의 최댓값, end는 모든 레슨들의 총합으로 저장합니다.
• start가 end보다 커질 때까지 밑의 과정을 반복합니다.
  - 배열을 순회하며 sum(레슨들의 합)+A[i](현재 레슨값)가 middle(중간값)보다 큰지 확인합니다.
  - 크다면 count(M의 갯수)를 하나 올려주고 sum을 0으로 만들어줍니다.
  - 배열에 있는 레슨을 차례로 sum에 더해줍니다.
  - 만약 sum이 0이 아니면 count를 하나 올려줍니다.
  - count가 M보다 크다면 start에 중간값+1을 대입해줍니다.
  - count가 M보다 작다면 end에 중간값-1을 대입해줍니다.
• start값을 출력합니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] A = new int[N];
        int start = 0;
        int end = 0;

        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
            if (start < A[i]) {     //레슨 최댓값을 시작 인덱스로 저장하기
                start = A[i];
            }
            end += A[i];    //모든 레슨들의 총합을 종료 인덱스로 저장하기
        }

        while (start <= end) {
            int middle = (start + end) / 2;
            int sum = 0;
            int count = 0;

            for (int i = 0; i < N; i++) {   //middle 값으로 모든 레슨을 저장할 수 있는지 확인
                if (sum + A[i] > middle) {
                    count++;
                    sum = 0;
                }
                sum = sum + A[i];
            }
            
            if (sum != 0) {
                count++;
            }
            
            if (count > M) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        System.out.println(start);
        scanner.close();
    }
}

정리

"블루레이의 크기가 모두 같고 녹화순서가 바뀌지 않아야 함."이라는 문제의 조건이 이진 탐색 알고리즘을 사용하라는 의미이다. 이진 탐색을 이용하여서 블루레이의 최솟값을 찾아야 하는데 이 때 시작 인덱스가 최대 길이의 레슨이고, 마지막 인덱스가 레슨들의 총합인 점이 이 문제의 포인트이다. 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다.
자료가 정렬되어 있다면 탐색할 때 이진 탐색을 이용하자!