[백준] 17951. 흩날리는 시험지 속에서 내 평점이 느껴진거야

문제 링크

[백준] 17951. 흩날리는 시험지 속에서 내 평점이 느껴진거야

풀이 과정

이분 탐색 문제입니다.

while (low <= high) {
    int mid = (low + high) / 2;
    int cnt = 1, sum = 0, min = Integer.MAX_VALUE;

    for (int i = 0; i < N; i++) {
        sum += correct[i];

        if (sum >= mid) {
            cnt++;
            min = Math.min(min, sum);
            sum = 0;
        }
    }

    if (cnt > K) low = mid + 1;
    else high = mid - 1;
}

1. mid 값을 그룹 내 맞은 개수의 총합 상한선으로 설정한 뒤, 그룹 개수를 셉니다.
2. 그룹 개수 cnt가 문제에서 주어진 나눌 그룹의 수 K보다 크다면 lower bound를 조정하고, 그렇지 않다면 upper bound를 조정합니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] correct = new int[N];
        int low = 0, high = 0;

        for (int i = 0; i < N; i++) {
            correct[i] = sc.nextInt();
            high += correct[i];
        }

        while (low <= high) {
            int mid = (low + high) / 2;
            int cnt = 1, sum = 0, min = Integer.MAX_VALUE;

            for (int i = 0; i < N; i++) {
                sum += correct[i];

                if (sum >= mid) {
                    cnt++;
                    min = Math.min(min, sum);
                    sum = 0;
                }
            }

            if (cnt > K) low = mid + 1;
            else high = mid - 1;
        }

        System.out.println(low - 1);
    }
}