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



예산



아 parametric search 구나


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




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


전자는


1
2
3
4
5
6
7
8
9
10
int l = -1000000000;
int r = 1000000000;
 
while (l < r) {
    int mid = (l + r) >> 1;
    if (q(10, n - 1, i - 1, j - 1, mid) >= k)
        r = mid;
    else
        l = mid + 1;
}
cs

후자

후자는


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
cs



와 같다.




전자의 경우 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)인 코드를 많이 봐왔던지라 차이점이 궁금해지긴 한다.


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


풀 코드는 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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);
}
cs


+ Recent posts