탐색 알고리즘 문제 풀어보기 5(백준 2343번 기타 레슨)

이번에는 이진탐색을 이용해 문제를 풀어보자.

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

2343번: 기타 레슨

이 문제는 여러 자연수와 최대 그룹수가 주어지면 그 자연수들을 그룹으로 묶을 때 그룹의 최소크기를 구하는 문제이다. 단 숫자들에게는 순서가 있어 이 순서가 유지되며 묶어야 한다는 조건이 있다. 순서가 있다는 조건에서 이진 탐색을 써야겠다는 생각을 해야 하는 문제이다.

문제를 해결하기 위해서는 가능한 그룹의 크기를 범위로 지정해 놓고 직접 해보면서 그룹의 크기를 조절해나가야 한다. 만약 그룹 크기의 범위가 10~20이라면 처음에 15를 해보고 여유로우면 12를 해보고 안되면 14를 해보는 이런 이진탐색의 과정이 필요하다.

그룹 크기의 범위는 최소가 자연수의 최댓값이고 최대가 모든 자연수의 합이다. 주어진 숫자보다 작은 그룹크기는 숫자를 못 넣으니 의미가 없고 모든 숫자를 더했을 때보다 큰 그룹크기도 의미가 없기 때문이다.

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

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)));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] array = new int[N+1];
        int big = 0;
        int num;
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++){
            num = Integer.parseInt(st.nextToken());
            if(num>big) big = num;
            array[i] = array[i-1] + num;
        }
        int start = big;
        int end = array[N] + start;
        int pivot;
        int cnt;
        int pre;
        while(start<=end){
            cnt = 1;
            pre = 0;
            pivot = (start+end)/2;
            for(int i=1;i<=N;i++){
                if(array[i]-array[pre]>pivot){
                    cnt++;
                    pre = i-1;
                }
            }
            if(cnt<=M) end = pivot - 1;
            else start = pivot + 1;
        }
        bw.write(start+"");
        bw.flush();
        bw.close();
    }
}

먼저 입력들은 배열에 넣어주었고 누적합을 이용하였다. 수들을 묶을 때 연속된 숫자들만 묶임으로 누적합을 이용하면 더 빠르게 연산이 가능할 것이라고 생각했다. 최댓값은 명령어로 구해도 되지만 반복문을 돌면서 구하게 하였다. 그룹 크기의 범위는 시작이 수의 최댓값, 끝이 누적합의 최댓값이다. 이제 투포인터를 이용하여 범위의 중간부터 하나씩 직접 계산해 보며 몇 개의 그룹이 나오는지 확인한다. 만약 그룹수가 입력받은 것보다 작거나 같다면 아직 여유롭다는 뜻이므로 그룹 크기를 줄이기 위해 종료 인덱스를 중간값-1로 바꿔준다. 여기서 등호를 안 넣으면 아직 더 최적화가 가능함에도 안 하는 경우가 발생할 수 있으니 주의한다. 만약 불가능하다면 시작인덱스를 중간값+1로 바꾸어 그룹 크기를 증가시켜 준다. 이것을 시작인덱스가 종료인덱스보다 커지거나 같아질 때까지 반복하고 그때 마지막으로 계산한 결과가 정답이다.

문제 자체는 어렵지 않지만 이진탐색을 이용한다는 아이디어를 떠올리는게 어려운 문제였다. 이제 탐색은 끝내고 다음 포스팅부터는 탐욕법(그리디) 알고리즘에 대해서 알아보도록 하겠다.