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

www.acmicpc.net/problem/17951

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

스터디할 때 풀었던 문제인데 왜 답이 right일까?를 고민하다가 이제 이유를 알아냈다

 

이진탐색 및 매개변수 탐색의 진행에는 loop-invarient라는 성질이 적용된다.

loop를 지속하게 하는 절대적인 조건이므로, loop가 시작되기 전 & loop 중 & loop 이후에도 정해진 loop-invarient는 유지되어야 한다.

이 문제(parametric search)에서는 parameter를 "각각의 그룹에 속한 시험지 점수의 합 S 중 최소값을 결정하는 기준 점수"로 설정했다

그래서 loop가 반복될 동안 두 가지 조건은 항상 성립한다

1. l은 r보다 작다
2. 그룹 기준 점수를 l로 했을 때 그룹의 개수는 k보다 크거나 같고, r로 했을 때 그룹의 개수는 k보다 작다

반복문이 종료될 때 까지 위의 두 가지 성질은 항상 만족되고, 종료된 순간 l과 r의 차이를 최소화 하는 범위를 찾아낸 것임이 확인된다.

따라서 우리가 찾는 답은 반복이 종료된 뒤의 l(r-1)이 되어야 한다.

#include <bits/stdc++.h>
#define MAX 2147483647
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k; cin >> n >> k;
    int ans = 0;
    int l = -1;
    int r = 0;
    vector<int> arr(n);

    for (int i = 0; i < n; i++)cin >> arr[i];

    for (int i = 0; i < n; i++)r += arr[i]; //총 합을 최댓값(r)으로 설정
    r++;
    //초기 l과 r값 = left 경계값과 right 경계값

    // parameter = k개의 그룹으로 나누었을 때, 그룹의 점수 합의 최소값
    // expected value = 그룹의 점수 합의 최소값을 최대로 하는 기준 점수 x
    // ✔그룹 기준 점수를 i+1로 했을 때 그룹의 개수 < k <= 그룹 기준 점수를 i로 했을 때 그룹의 개수
    
    // loop invariant에 의해 다음의 두 성질이 loop동안 유지됨
    // 1. l < r
    // 2. NumOfGroupsByScore(r) < k <= NumOfGroupsByScore(l)
    
    while (l+1 < r) {
        int cnt = 0;
        int sum = 0;
        int mid = (l + r) / 2;
        for (int i = 0; i < n; i++) {
            sum += arr[i]; //각 시험지의 점수를 더하고
            if (sum >= mid) { //설정한 기준 점수보다 sum값이 커지면 그룹을 분리함
                sum = 0; 
                cnt++; //그룹 개수 카운트
            }
        }

        if (cnt >= k) { //카운트한 그룹 개수가 k보다 크거나 같으면 기준 점수를 높여서 그룹의 개수를 더 적게 생성하는 범위로 좁힘
            l = mid;
        }

        if (cnt < k) { //카운트한 그룹 개수가 k보다 작으면 기준 점수를 낮춰서 그룹의 개수를 더 많이 생성하는 범위로 좁힘
            r = mid;
        }

    }
    // loop가 종료되었을 때 ✔를 만족하는 가장 큰 i를 찾아야 하므로 원하는 답이 l(r-1)임을 알 수 있다
    
    cout << l;
    return 0;
}

아직은 문제를 풀면서 동시에 검증할 수는 없겠지만 loop invarient 조건을 설정해주고 정답을 확인하는 용도로 활용할 수 있을 것 같다