[99클럽 코테 스터디 4일차 TIL / 백준] 2343 - 기타 레슨 (JAVA)

99클럽 코테스터디 4일차 TIL
KeyWord : BinarySearch, lower bound

문제

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

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

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

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

힌트

강의는 총 9개이고, 블루레이는 총 3개 가지고 있다.

1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에, 블루레이의 크기는 17이 된다. 17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.

---

풀이

이번에도 저번 문제와 마찬가지로 이분 탐색 카테고리에 속해있지만, 이분탐색을 어떻게 활용해야 할지 감이 영 안 잡혔던 문제였다.

주어지는 강의의 배열에 시선이 쏠리면 해결법이 안 떠오른다. 우리가 중요하게 봐야할 것은 강의 시간이다.

먼저, 블루레이의 최소 크기는 몇 분일까? 정답은 주어진 강의 시간 중 최댓값이다. 중간에 편집하여 자를 수 없으므로 당연한 이야기다. (블루레이의 개수는 신경쓰지 말고 생각하자.)

1 2 3 4 5 6 7 8 9

주어진 예제 입력을 기준으로, 블루레이는 최소 9분의 길이를 가져야 한다.

그렇다면 블루레이의 최대 길이는 어떻게 될까? 이것은 당연히 주어진 강의들을 모두 합한 시간이 된다. 여기서는 1~9까지 전부 더한, 45분이 될 것이다.

즉, 9~45의 사이에 문제의 해가 존재한다. 이 값 사이에서 이분 탐색을 진행하면 된다.

이제 이분 탐색의 종료 조건을 생각해보자.

이분탐색을 처음 진행했을 때, mid는 27이 된다. 이것은 블루레이 하나의 크기가 27분이라는 뜻이다. 그렇다면 27분짜리 블루레이 몇개를 사용해야 저 강의를 다 담을 수 있을지 생각해보자.

1 2 3 4 5 6
7 8 9

이렇게 두 개의 블루레이만 이용하면 강의를 다 담을 수 있게 된다. (이제부터 이 개수를 cnt라고 하자.) 이 cnt의 개수가 이분 탐색의 키가 된다.

cnt=2, M=3이므로 cnt<M이 된다. 즉, 블루레이가 너무 크다는 뜻이므로 hi를 내리면 된다. 반대로, cnt<M이라면 lo를 올리면 된다는 것까지는 자명하다.

그렇다면 cnt==M일 때를 생각해보자.

일반적인 이분탐색이었다면 이 경우 탐색이 종료되겠지만, 이 문제는 조건을 만족하는 해 중 최솟값을 찾아야 한다. 즉, lower bound를 이용해야 하므로 이때도 hi를 내려야 한다. (지금 찾은 해보다 더 작은 값이 존재할 수도 있다는 것을 생각하자.)

이제 구현만 하면 된다.

코드

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

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[] lectures = new int[n];  
        st = new StringTokenizer(br.readLine());  

        int sum = 0, max = 0;
        for (int i = 0; i < n; i++) {  
            lectures[i] = Integer.parseInt(st.nextToken());  
            sum += lectures[i];  
            max = Math.max(max, lectures[i]);  
        }

        int ans = binarySearch(lectures, max, sum + 1, m);  
        System.out.println(ans);  
    }

    private static int binarySearch(int[] lectures, int lo, int hi, int m) {  
        int mid;  
        while(lo < hi) {  
            mid = lo + (hi-lo)/2;

            int cnt = 1, total_time = 0;  
            for (int i = 0; i < lectures.length; i++) {  
                if(total_time + lectures[i] > mid) {  
                    cnt++;  
                    total_time = 0;  
                }
                total_time += lectures[i];  

                if(cnt > m) // 연산량을 줄이기 위한 가지치기
                    break;  
            }

            if(cnt <= m) {  
                hi = mid;  
            } else {  
                lo = mid+1;  
            }
        }
        return lo;  
    }  
}

 

---

 

회고

이 문제를 어떻게 이분 탐색으로 풀어낼 수 있는지 고민하는 것부터 시간을 많이 썼던 문제였다. 그래도 방법을 찾은 후, 구현할 때는 이전 문제의 경험 때문에 쉽게할 수 있었다.

사실, 이분 탐색의 해결법을 찾기 전에 백트래킹을 이용하여 먼저 구현했다. 주어진 예시로 치면 9개의 강의를 나누었을 때 나올 수 있는 모든 조합(ex) [1, 1, 8], [3, 2, 5] 등등)을 찾아 그 중 최솟값을 찾는 방식이었지만...

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

public class Main {
    static int answer = Integer.MAX_VALUE;
    static int n, m;
    static int[] lectures;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        lectures = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lectures[i] = Integer.parseInt(stk.nextToken());
        }

        arr = new int[m];
        backTracking(0, 0);
        System.out.println(answer);
    }

    static void backTracking(int depth, int len_chk) {
        if (depth == m) {
            if (len_chk == n) {
                int idx = 0, max = 0, tmp = 0;
                for (int i = 0; i < m; i++) {
                    tmp = 0;
                    for (int j = idx; j < arr[i] + idx; j++) {
                        tmp += lectures[j];
                    }
                    max = Math.max(max, tmp);
                    idx += arr[i];
                }
                answer = Math.min(answer, max);
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (len_chk + i > n) continue; // 가지치기
            arr[depth] = i; // 현재 블루레이 길이 저장
            backTracking(depth + 1, len_chk + i);
        }
    }
}

결과는 당연히 시간 초과. M이 100000이 되면, 100000자리 수열이 만들어지므로 당연한 결과다.