[백준] 기타 레슨(2343)

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

블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 한다는 점이 이진 탐색을 생각해 볼 수 있는 단서가 된다.

블루레이에 첫 번째 레슨부터 마지막 레슨까지 차례대로 저장해 보면서, 모두 저장할 수 있다면 블루레이 크기를 줄이고, 모두 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 접근하는 것이다.

조금 더 직관적인 예시를 들자면, 다양한 크기의 책을 박스에 담는다고 가정해보자.

여기서 박스는 최대한 작은 크기를 사용해야한다.

박스 크기가 너무 작아서 모든 책을 담았을 때 주어진 박스의 개수(블루레이 개수)보다 더 많이 필요하다면 박스의 크기를 키워야 한다.

# 블루레이 크기가 작다는 의미이니 현재 블루레이 사이즈보다 큰 사이즈로 변경
if count > M:
	start_size = mid_size + 1

반대로 박스 크기가 충분히 커서 책을 모두 담았는데, 박스 크기가 남아있을 가능성이 있으므로 더 작은 박스의 크기로 시도한다.

# 블루레이 크기가 너무 크다는 의미이니 현재 블루레이 사이즈보다 작은 사이즈로 변경
else:
	end_size = mid_size - 1

그렇다면 블루레이 크기 범위는 어디서부터 어디까지 잡아야 하는지게 관건이 된다.

잘 생각해보면 시작 사이즈(최소 사이즈)는 입력받은 레슨 길이 중 가장 큰 사이즈(최댓값)가 시작 사이즈가 될 것이다.

왜냐하면 블루레이는 최소한 1개의 레슨은 담겨야 하기 때문이다. 따라서 start_size는 아래와 같이 초기화를 진행한다.

start_size = max(lesson)

반대로 마지막 사이즈(최대 사이즈)는 이진 탐색을 시작하기 전에 모든 레슨의 길이를 더한 값으로 잡아주면 된다.

이 말은 즉슨 1개의 블루레이로 모든 레슨을 담을 수 있다는 의미가 되기 때문이다. 따라서 end_size는 아래와 같이 초기화를 진행한다.

end_size = sum(lesson)

Python

따라서 파이썬의 전체 소스코드는 다음과 같다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
lesson = list(map(int, input().split()))

start_size = 0
end_size = 0

for i in lesson:
    # 시작 사이즈는 레슨 리스트에서 길이가 가장 긴 강의
    if start_size < i:
        start_size = i
    
    # 마지막 사이즈는 레슨 리스트의 모든 강의길이의 합
    end_size += i

# 시작 사이즈가 마지막 사이즈보다 작거나 같을 동안 반복
while start_size <= end_size:
    # 중간 사이즈 (현재 블루레이 사이즈)를 구하여 이분탐색에 활용
    mid_size = int((start_size + end_size) / 2)
    sum = 0 # 현재 블루레이(i번째 블루레이)에 담은 강의길이의 합
    count = 0 # 사용한 블루레이의 수

    for i in range(N):
        # 각 강의들을 순서대로 더해보면서 중간사이즈보다 큰지 비교
        if sum + lesson[i] > mid_size:
            # 중간사이즈보다 크다면 추가 블루레이가 필요
            count += 1
            sum = 0 # 블루레이 길이 초기화
        
        # 강의를 블루레이에 더함
        sum += lesson[i]
    
    # 아직 처리 못하고 남은 강의가 있다면
    if sum != 0:
        count += 1 # 블루레이 1개 추가
    
    # 블루레이 개수가 문제에서 요구하는 블루레이 개수보다 더 많다면
    if count > M:
        # 블루레이 크기가 작다는 의미이니 현재 블루레이 사이즈보다 큰 사이즈로 변경
        start_size = mid_size + 1
    else:
        # 블루레이 크기가 너무 크다는 의미이니 현재 블루레이 사이즈보다 작은 사이즈로 변경
        end_size = mid_size - 1

print(start_size)

Java

안타깝게도 자바의 경우 파이썬처럼 쉽게 바로 max, min을 구하는 함수가 존재하지 않는다...

따라서 반복문을 통해 최대값, 최솟값을 찾거나, 아니면 이래와 같이stream API를 활용해서 바로 구할 수 있다.

int start = Arrays.stream(A).max().getAsInt();
int end = Arrays.stream(A).sum();

이후 사용하는 알고리즘은 파이썬과 동일하다.
따라서 전체 소스코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P_2343 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] A = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int start = Arrays.stream(A).max().getAsInt(); // 시작 사이즈는 레슨 리스트에서 길이가 가장 긴 강의
        int end = Arrays.stream(A).sum(); // 마지막 사이즈는 레슨 리스트 길이의 총 합계

		// 이분탐색 조건: start가 end보다 작거나 같을 동안
        while (start <= end) {
            int mid = (start + end) / 2;

            int sum = 0;
            int count = 0;

            for (int i = 0; i < N; i++) {
                if (sum + A[i] > mid) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }

			// 아직 처리하지 못하고 남은 강의가 있는 경우
            if (sum != 0) {
                count++;
            }

            if (count > M)
                start = mid + 1;
            else
                end = mid - 1;
        }

        System.out.println(start);
    }
}

한 가지 주의할 점은 코드 흐름 상, for문 종료 후 i번째 블루레이에 담은 레슨 길이의 총합을 나타내는 변수인 sum에 값이 남아있다면 블루레이를 1개 더 추가해 주어야 한다.