백준 2343번 : 기타 레슨

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

이분탐색이 코테문제로 많이 나오는거 같은데 이분탐색 문제가 익숙하지 못하다. 그래서 이분탐색 문제를 집중적으로 풀어보는데, 해당문제가 생각할 거리가 많아서 기록을 해두기로 했다.

 

문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

 

import java.util.*;
import java.io.*;

public class Main {
    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[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        int left = 0;
        int right = 0;
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if(arr[i]>left) left = arr[i];
            right += arr[i];
        }
        //end input

        while(left<=right) {
            int mid = left+(right-left)/2;

            int sum = 0;
            int cnt = 0;

            for(int i=0; i<N; i++) {
                if(cnt>M) break;
                if(sum+arr[i]>mid) {
                    sum=0;
                    cnt++;
                }
                sum += arr[i];
            }
            if(sum!=0) cnt++;
            //right뒤쪽에 있는 값들은 전부 정답이라 할 수 있기에 최소값을 구하려면 같은 경우에도 right 뒤쪽으로 옮겨줘야한다.
            if(cnt<=M) right = mid-1;
            else left = mid+1;
        }
        System.out.println(left);
    }//end main
}

 

헤맸던 부분

1. 이분탐색할 대상과 최대값은 잘 설정했었는데, 최소값 설정을 1로 뒀다.
--> 1로 설정하게 되면 강의의 길이보다 블루레이가 작은데도 카운트가 된다.

 

2. right뒤에 있는 값들은 모두 조건에 만족하는 수들이다.(최소값이 아닐 뿐) 그렇기에 cnt와 M이 같은 경우에도 right뒤로 넘겨서 left가 right뒤로 넘어간 순간 left가 답이 된다.

 

3. 이분탐색시 큰값 처리를 위해서 mid값을 설정할 때 left+(right-left)/2를 해주는데.. left+(right-left) 만 써놓고 계속 시간초과가 떠서 1시간은 쓴거 같다...꼼꼼하게 보도록하자..