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(1, 0, 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 |
'알고리즘 > 미분류' 카테고리의 다른 글
| codeforces educational 50 round div2 참여기록 (0) | 2018.09.09 |
|---|---|
| SCC 문제들! 백준) 2150, 4013, 4196 (0) | 2018.07.22 |
| 백준) 11003 최소값 찾기 (0) | 2018.07.13 |
| 중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘 (0) | 2018.02.22 |
| 백준) 2257 화학식량 (0) | 2018.01.31 |