백준) 2512 예산

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

예산

아 parametric search 구나

라고는 빨리 알았지만, 이분탐색의 늪에 빠졌다가 뭔가 깨달음을 얻어서 여기에 옮기고자 한다.

k번째 숫자(https://www.acmicpc.net/problem/7469)를 parametric search로 풀고, 이 문제도 parametric search로 풀었다.

전자는

int l = -1000000000;
int r = 1000000000;
 
while (l < r) {
    int mid = (l + r) >> 1;
    if (q(1, 0, n - 1, i - 1, j - 1, mid) >= k)
        r = mid;
    else
        l = mid + 1;
}

후자

후자는

while (l < r) {
    int mid = (l + r + 1) / 2;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] >= mid)
            sum += mid;
        else
            sum += arr[i];
    }
 
    if (sum <= m)
        l = mid;
    else
        r = mid - 1;
}

와 같다.

전자의 경우 mid가 성공했다면, 그 값을 포함한채 오른쪽을 좁혀야 하고,

(k번째 숫자를 찾아야 하므로, 더 큰 값은 의미가 없고, mid는 정답일 수 있으므로 버리면 안된다.)

후자의 경우 mid가 성공했으면, 그 값을 포함한채 왼쪽을 좁혀야 한다.

(최대 예산액을 찾아야 하므로, 작은 값은 의미가 없으며, mid는 정답일 수 있으므로 버리면 안된다.)

따라서 left와 right로 mid를 정하는 기준이 달라지는데, 이유를 말로 하긴 복잡하니까 그림으로 설명해보겠다.

mid 를 (left + right) / 2 로 하느냐, (left + right + 1) / 2로 하느냐의 차이점은, (성공했을 때 좌우를 변경하는 로직이 완벽했을 때)

결국엔 range가 2일 때 선명하게 드러나는데,

이번 예산 문제의 경우 mid 를 (left + right) / 2 로 하고 성공했을 경우, 

위 그림과 같이 무한루프에 빠지게 된다. 

반대로 k번째 숫자 문제는,

mid 를 (left + right + 1) / 2 로 한다면 성공했을 경우 무한루프에 빠지게 된다.

따라서 좌우를 버리는 로직을 완벽히 세워놨다면, 모든 parametric search를 위 두 케이스 중에 알맞은 케이스로 풀면 된다

라는게 내린 결론인데, 평소 while(left <= right)인 코드를 많이 봐왔던지라 차이점이 궁금해지긴 한다.

정파말고 사파식 공부를 하는 중이라 깊이가 모자른걸 요새 크게 통감하고 있다 ㅎㅎ;

풀 코드는 다음과 같다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, m;
int arr[10000];
 
int main() {
    int l = 1, r = 0;
 
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
        r = max(r, arr[i]);
    }
    scanf("%d", &m);
 
    while (l < r) {
        int mid = (l + r + 1) / 2;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (arr[i] >= mid)
                sum += mid;
            else
                sum += arr[i];
        }
 
        if (sum <= m)
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d", l);
}