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

문제

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

N개의 시험지와 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 <= K <= N <= 100,000)

그리고 N개의 시험지에 대한 맞은 문제의 개수가 주어진다.

획득할 수 있는 점수는 맞은 문제 개수의 합이다.

시험지를 K개로 나눈 그룹의 점수 중, 최소가 되는 그룹의 합 중 최댓값을 구해야 한다.

 

풀이

이분 탐색을 사용하여 가능한 최솟값의 범위를 줄여 나간다.

mid 이상 되는 그룹을 몇 개 만들 수 있는지를 세어보고, 그 개수가 k 이상이면 이 mid는 가능한 값으로 간주한다.

mid의 범위는 획득할 수 있는 점수가 된다.

• 최소로 획득할 수 있는 점수(left)는 시험지 점수 중 가장 작은 값으로 설정해주었다. (그룹 하나의 점수가 0이 될 수 있으므로 0으로 설정해줘도 무방)
• 최대로 획득할 수 있는 점수(right)는 모든 시험지의 점수를 합한 값이 된다.

 

현재 mid를 기준으로 그룹을 나눴을 때,

• 그룹의 개수가 k 이상이면, 현재 mid는 최댓값의 후보가 되고, 더 큰 값도 가능한지 확인하기 위해 left = mid + 1
• 그룹의 개수가 k보다 작으면, mid가 너무 커서 그룹을 많이 만들 수 없으므로 right = mid - 1

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] scores = new int[n];
        st = new StringTokenizer(br.readLine());
        int left = 0;
        int right = 0;
        for (int i = 0; i < n; i++) {
            int score = Integer.parseInt(st.nextToken());
            scores[i] = score;
            left = Math.min(left, score);
            right += score;
        }

        int answer = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            
            int group = 0;
            int currentSum = 0;
            for (int i = 0; i < n; i++) {
                currentSum += scores[i];
                if (currentSum >= mid) {
                    group++;
                    currentSum = 0;
                }
            }

            if (group >= k) {
                left = mid + 1;
                answer = mid;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(answer);
    }

}