[BOJ][Java]Q17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

문제 풀이

이런 류의 이분탐색 문제를 접하면,
주어진 배열에서 left right로 범위를 나누어 탐색하려 했는데 아무리 생각해도 알고리즘을 생각해내기 힘들 경우,

높은 확률로 이 문제처럼 배열이 아닌 "찾고자 하는 값의 범위"를 이분탐색해야한다.

이 점을 염두에 두고 풀이하면 실마리를 찾기가 보다 수월하다.
(나만 맨날 이거 헷갈리는 걸 수도 있음)

 

그룹 중 최소값이 최대가 되는 최적해를 이분탐색으로 찾는다.

범위의 left는 원소 중 최소값(어쨌든 원소 하나는 무조건 포함하므로), right는 모든 원소의 합이다. 

 

mid를 구했으면, mid가 그룹 중 최소값일 경우 그룹의 개수가 k개 이상인지 검사한다.

k개 이상의 그룹을 만드는 것이 가능하면, 더 큰 최적해가 있는지 찾아본다 -> left를 mid+1로 이동

불가능하면, 더 작은 최적해가 있는지 찾아본다 -> right을 mid-1로 이동

 

그룹의 개수가 k개인지 알아보는 방법?

최소값이 mid라면, 모든 그룹은 당연히 mid보다 같거나 커야 한다.

Index 0부터 증가시키며 배열을 탐색하는데, 원소의 합이 mid보다 같거나 커지면 그룹을 나눈다.

사실 거기서 끊지 않고 다음 원소까지 포함해도 원소의 합은 mid보다 같거나 크다. 

하지만 왼쪽부터 최대한 적은 수의 원소를 채우며 그룹을 나누는 것인데,

그 이유는 어차피 더 많은 수의 원소를 가진 그룹이 있다면 mid가 더 큰 경우의 검사를 할 때 검사되기 때문이다.

---

코드

package 이분탐색;

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

public class Q17951_흩날리는시험지속에서내평점이느껴진거야 {
    /*[골드4]Q17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야*/
    /* 요약
    그룹 중 최소값이 최대가 되는 최적해를 이분탐색으로 찾는다.
    왼쪽부터 최대한 적은 원소를 채우며, 그룹 개수 k가 가능한지 찾는다.
     */
    static int n, k;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        arr = new int[n];

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

        int left = min;
        int right = sum;

        while(left<=right){
            int mid = (left+right)/2;
            //그룹이 k개 만들어지는 것이 가능하면
            //더 큰 최적해가 있는지 찾아보아야 하므로, mid보다 큰 범위를 탐색한다.
            if(isPossible(mid)){
                left = mid+1;
            }else{
                //불가능하면 더 작은 최적해 범위를 탐색한다.
                right = mid-1;
            }
        }
        System.out.println(right);
    }
    static boolean isPossible(int mid){
        //합이 가장 작은 그룹의 합이 mid여야 함 -> 모든 그룹의 합이 mid보다 같거나 커야 함
        int sum = 0;
        int groupCnt = 0;
        //왼쪽부터 최대한 적은 개수의 원소를 채우며 그룹 개수를 센다.
        //어차피 더 큰 최적해가 있다면 다음 검사에서 나올 테니까.
        for(int i = 0; i<n; i++){
            sum+=arr[i];
            if(sum>=mid){   //최대한 적은 개수의 원소를 채우므로, mid보다 같거나 커지면 그룹을 자른다.
                sum = 0;
                groupCnt++;
            }
        }
        return groupCnt >= k;
    }
}