[자바] 백준 2343 - 기타 레슨 (java)

목차

문제 : boj2343

 

 

필요 알고리즘

• 매개 변수 탐색 (parametric search), 이분 탐색 (binary search)
  
  • 이분 탐색을 응용한 매개 변수 탐색을 사용해 푸는 문제이다. 이런류는 매개 변수 탐색할 값에 대한 정의만 잘 세우면 갑자기 문제가 쉬워진다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  일단 순차적으로 생각해보자.

 

1. 우선 isPossible(int limit) 이라는 함수를 생각해보자. 이건 'limit' 이라는 값 이하로 M개로 값을 쪼갤 수 있는지 판단하는 함수이다.

 

2. 그렇다면 limit 값의 최소치는 어떻게 될까? 우선 강의 1개는 원자적이므로, 강의 1개 중 최대의 강의 길이보다는 커야한다. 또한 N/M(올림) 보다도 커야 한다.

for (int i = 0; i < n; i++) max = max(max, arr[i] = Integer.parseInt(st.nextToken()));

int start = max(max, n/m+(n%m==0?0:1));

 

3. 자 그럼 저 start라는 값부터 시작해서 +1씩 증가시키면서 isPossible(start)를 보다가, true가 뜨는 순간이 답이 된다!! 이론적으론 그런데, 문제는 isPossible의 시간복잡도가 O(N) 이다. 그리고 이론상 나올 수 있는 limit의 최대치는 N*10000 이다. 따라서 O(10000 * N^2) 이 되므로 시간초과가 된다.

 

4. 그러므로 limit이라는 값을 찾기 위해 매개 변수 탐색을 사용해준다. 위에서 정한 start 값부터, 이론상 최대치인 10억까지 진행해주면 된다. '10억 = N의 최대치 100000 * 각 강의의 길이 최대치 10000' 이다. 참고로 실제 최대치는 N개의 입력값의 합이긴 한데, 어차피 매개 변수 탐색을 할 것이므로 시간 복잡도에 영향은 딱히 없다. 실제로도 제출해보니 1ms도 차이 안났다. isPossible이 true면 end를 낮추고, false면 start를 높이는 식으로 답을 찾을 때 까지 이분 탐색을 진행하는거다.

int start = max(max, n/m+(n%m==0?0:1));
int end = 1000000000;
while (start<=end) {
    int mid = (start+end)/2;
    if (!isPossible(mid))
        start = mid+1;
    else
        end = mid-1;
}

 

 

코드 : github

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

import static java.lang.Math.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    int n, m;
    int[] arr;

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) max = max(max, arr[i] = Integer.parseInt(st.nextToken()));

        int start = max(max, n/m+(n%m==0?0:1));
        int end = 1000000000;
        while (start<=end) {
            int mid = (start+end)/2;
            if (!isPossible(mid))
                start = mid+1;
            else
                end = mid-1;
        }

        System.out.println(start);
    }

    private boolean isPossible(final int limit) {
        int idx = 0;
        for (int i = 0; i < m; i++) {
            int sum = 0;
            while (idx<n && sum <= limit) {
                if (sum+arr[idx] > limit) break;
                sum += arr[idx++];
            }
        }
        return idx == n;
    }
}