이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 77 번째 글 입니다.
목차
실버1 : 이분 탐색, Parametric Search 문제이다.
생각
처음에 이 문제를 풀 때, 세그먼트 트리로 풀려고 했다. 그런데, 문제가 생겼다. 그렇게 구현하려면, 100000개 를 50000개의 블루레이에 담으려고 한다면 계속해서 재귀 함수를 타고 들어가며 구해야 한다. 시간 제한이 2초이고, 또한 재귀함수의 depth가 너무 깊어져 이 방향으로 문제를 해결하면 안된다고 판단했다.
고민을 하던 중, 답을 먼저 제안하고, 이 답을 기반으로 역으로 추적하면 어떨까하는 생각이 들었다. 이 방법을 파라메트릭 서치(parametric Search)라 한다.
Parametric Search
최적화 문제를 결정 문제로 바꾸어 해결한다.
이진 탐색과 비슷한 방법이다. 그런데 어떤 상황에서 사용하는지 알아야 한다. 위의 문제는 결국, N개의 입력이 들어왔을 때, 이걸 M개로 나누고, M개로 나눈 각각의 뭉텅이들 사이에서 최댓값들을 뽑아 그것의 최솟값을 구하는 문제이다. (응?)
- 입력 N을 M개의 집합으로 자른다. 다양한 가지수로 자를 수 있다. 이 가지수를 K라 하자.
- 그 집합들의 합을 갖고 있는다.
- 그 요소들을 가지는 집합 L를 만든다. (K의 요소 개수는 M개, 발생하는 집합 L의 개수는 K개)
- 발생한 모든 L 집합에 대해 요소들의 최댓값을 구한다. 그 최댓값을 모은 집합을 P라 하자. (P의 요소 개수는 K개)
- P집합의 요소들 중 최소값을 구한다.
완전 탐색을 한다면 위와 같이 할 수 있을 것이다. 그런데, 결국 이 문제는 최적의 디스크 크기를 구하는 문제이다. 이런 문제에서 새로운 발상을 할 수 있는데, 답은 제안하는 것이다.
방법
이 문제에서 내가 원하는 것은 disk 크기를 구하는 것이다. 이 disk 크기가 될 수 있는 최솟값과 최댓값을 계산해보자. N = 100000 이고, 각각의 동영상 용량은 10000이 최대이므로, 이 동영상 모두를 한 disk에 넣는다면 1000000000크기가 최대이다. 일단 이해를 하는 과정이기에 최댓값을 100이라 가정하겠다.
과정은 이분 탐색과 비슷하다. 답이 될 수 있는 최소, 최대에서 반이 답이 되는지 되지 않는지 판단한다.
너무 디스크 크기가 작다면 오른쪽을 탐색한다.
너무 디스크 크기가 크다면 왼쪽을 탐색한다.
위의 과정을 반복하여 답을 도출한다.
결국 위 방법의 핵심은, 원하는 답의 범위를 설정하고 이 값이 되는지 안되는지를 파악한다. 이다. 이러한 방법을 사용하기로 마음 먹었다면, 어떠한 조건에서 탐색의 방향을 바꿀 수 있는지, 해당 문제의 특징은 무엇인지 확인해야 한다.
문제의 특징
M개의 disk를 사용했을 때, disk 크기가 가장 줄어들 수 있다.
- 만약 10개의 disk를 사용할 수 있다고 하자. 그렇다면 답은 N을 10개로 나누었을 때 가장 작게 나눌 수 있다.
- 물론 10개보다 적은 수의 disk를 사용해서 나누었을 때 10개를 사용했을 때의 답과 같게 나올 수는 있다.
- 따라서 10개보다 적은 수의 disk를 사용할 경우에도 답을 업데이트 해주는 대상이 된다.
- 또한 M개의 disk를 사용할 수 있는 모든 경우의 수를 비교해야 한다.
처음에 M개로만 나뉘면 답이라 해서 틀렸다. ㅠ
탐색 조건
제시한 블루레이 Size를 가지고 만들었을 때 나온 값이 M보다 크면 Size를 키운다.
제시한 Size를 가지고 N를 최대한 나눈 결과 가지고 있는 블루레이 갯수(M)보다 disk가 더 필요하다는 결론이 나오면, 현재 disk 사이즈가 너무 작아 더 필요로 한다는 결론이다. 따라서 disk 크기를 키워야 한다.
제시한 블루레이 Size를 가지고 만들었을 때 나온 값이 M보다 작으면 지금 제시한 값을 업데이트 한다.
나온 값과 이전에 탐색한 답 중 최솟값으로 업데이트 한다.
제시하는 답은 video의 값보다는 항상 같거나 커야한다.
1 2 3 4 5 라는 video가 들어온다고 가정하자. 이 때, 내가 제시하는 답은 5보다 항상 같거나 커야 한다. 만약 3이라는 답을 제시한다면 4와 5는 disk에 들어갈 수도 없으므로 논리에서 벗어난다.
Code
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int video[100000];
int N, M, ans = 1e9;
bool isOk(int value){
int sum = 0, count = 1;
for (int i = 0; i < N; i++) {
if (value < video[i]) return false;
if (sum + video[i] > value) {
sum = video[i];
count++;
}
else sum += video[i];
if (count > M) return false;
}
return true;
}
int main(){
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> video[i];
}
int left = 0, right = 1e9;
while (left <= right) {
int mid = (left+right)/2;
if (isOk(mid)) {
ans = min(ans, mid);
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << '\n';
}