BOJ 17951 : 흩날리는 시험지 속에서 내 평점이 느껴진거야

풀이 상세

이분 탐색 (구글링 했음)

풀이 요약

1. 총 sum 값을 기준으로, mid 값을 기준으로 K만큼 그룹이 이루어지는 지 탐색한다.

2. K개로 그룹을 이루는 가운데 가장 최대로 나올 수 있는 값을 구하는 것이기에, 증가를 담당하는 l 을 기준으로 탐색한다.

3. 이분탐색이 이루어질 수록, cnt 와 K 의 범위가 근접해질 것이며, cnt==K 에 도달하는 것들 가운데, 최소의 값이 나타낼 수 있는 가장 큰 값을 반환하게 될 것이다.

배운점

• 이분탐색에 매우 약하다는 것을 알겠다. 근데, 코테에서는 한번도 만나본 적은 없는 거 같다, mid 의 기준을 idx 가 아닌 것으로 잡아, 계산을 하는 것은 처음 보는 듯 하다. 아님 했는데 잊어버렸거나
• 더불어 꽤 다양한 방식으로 이분탐색을 할 수 있다는 것을 생각하니, 머리가 핑 돈다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stk;
    static int N,K,l,r,arr[],min;
    private static void input() throws Exception{
        stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());
        arr = new int[N];
        stk = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
            r+=arr[i];
        }

    }
    private static void solve() {
        while(l<=r) {
            int mid = (l+r)/2;
            if(check(mid)) {
                min = mid;
                l= mid+1;
            } else {
                r = mid-1;
            }
        }
    }

    private static boolean check(int num) {
        int sum =0;
        int cnt =0;
        for(int i=0; i<N; i++) {
            sum +=arr[i];
            if(sum >=num) {
                cnt++;
                sum = 0;
            }
        }
        return cnt >= K;
    }

    private static void output() {
        System.out.println(min);
    }
    public static void main(String[] args) throws Exception{
        input();
        solve();
        output();
    }
}