[Algorithm] 99클럽 코테 스터디 4일차 TIL BOJ 2343

문제

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

풀이

문제 분석

• 문제를 풀기위한 과정을 정리하면 다음과 같다

1. 입력을 받는다
  - 각 강의의 길이를 받는 순간에 start와 end를 업데이트한다
  - start: 주어진 강의들 중 가장 긴 길이의 강의
  - end: 모든 강의 길이의 합
2. 이분탐색을 통해 mid 값이 blueray에 담을 수 있는 강의 길이라고 생각하고 주어진 강의들을 분배하여 필요한 blueray의 개수를 구한다
3. blueray가 M(사용할 수 있는 블루레이의 개수)보다 크다면 start를 mid+1로 증가시킨다
 - 반대라면 end를 mid-1로 업데이트한다
4. 탐색이 끝난 후 start에 저장된 값을 출력한다 (최소값을 출력해야하므로)

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] token = br.readLine().split(" ");
        int N = Integer.parseInt(token[0]); // N개의 강의
        int M = Integer.parseInt(token[1]); // M개의 블루레이
        int start = 0; // 강의 중 제일 긴 강의
        int end = 0; // 강의의 모든 합을 구해야 함
        int[] lecture = new int[N];
        String[] inputs = br.readLine().split(" ");

        for(int i = 0; i < N; i++) {
            lecture[i] = Integer.parseInt(inputs[i]);
            if(lecture[i] >  start) start = lecture[i];
            end += lecture[i];
        }

        while(start <= end) {
            int mid = (start + end) / 2;
            int sum = 0;
            int blueray = 0;

            for(int i=0; i<N ; i++) {
                if(sum + lecture[i] > mid) { // 새로운 강의를 현재 블루레이에 담을 수 있는지 확인
                  sum = 0;
                  blueray++;
                }
                sum += lecture[i];
            }
            if(sum != 0) { // sum이 0이 아닐 경우 sum에 남은 강의들을 저장하기 위한 블루레이를 한 개 더 추가해야 함
                blueray++;
            }
            if(blueray > M) {
                start = mid+1;
            }
            else {
                end = mid-1;
            }
        }
        bw.write(String.valueOf(start));
        bw.flush();
        bw.close();
    }
}

TIL

오늘 문제는 이분 탐색의 대상이 입력값이 아니었다는 점에서 어려웠다

한 블루레이에 들어갈 수 있는 최소값이 주어진 강의 중 길이가 가장 긴 강의여야 했고 최대값은 모든 강의의 합이어야 했다
또한 주어진 입력값을 저장한 배열을 대상으로 이분탐색을 적용하는 것이 아닌 위에서 구한 최소값과 최대값의 범위 내에서 가능한 블루레이의 크기를 찾았어야했다

오늘까지 이분탐색과 관련된 4가지 문제를 풀어보았는데, 길이, 분(시간) 등 연속된 개념 내에서 이분탐색을 하는 문제가 많은 것 같다는 생각이 들었다