문제
https://www.acmicpc.net/problem/2512
국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가 예산의 총액은 미리 정해져 있어서 모든 예산 요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
- 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
- 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정한다.
예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.
여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
입력
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 1만 이하이다.
다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다.
그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 10억 이하이다.
출력
첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.
예제
풀이
아래와 같이 모든 테스트 케이스를 고려하여 그대로 코드로 구현해보았다.
브루트포스 : O(N^2)
종료 조건 1 (가장 일반적인 경우)
종료 조건 2 (cur가 0까지 줄어든 경우)
종료 조건 3 (다 더해도 m을 안 넘는 경우)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[10001];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; // 지방 개수 (최대 1만)
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i]; // 최대 10만
}
int m; // 총 예산 (최대 10억)
cin >> m;
sort(arr, arr + n);
int temp = 0;
for(int i = 0; i < n; i++){ // 최대 1만
temp += arr[i];
// 누적합이 총예산을 넘으면 stop!
if(temp > m){
int cur = i; // 현재 인덱스 저장
// cur 하나씩 줄이면서 상한액 구하기
for(int cur = i; cur >= 0; cur--){ // 최대 1만
// 0~(cur-1)까지의 합 구하기
int psum = 0;
for(int j = 0; j < cur; j++){
psum += arr[j];
}
// 임시 상한액 = (m - 누적합) / 남은 개수
int result = (m - psum) / (n - cur);
// 임시 상한액 >= 바로 앞의 금액 (종료 조건 1)
if(result >= arr[cur - 1]){
// 상한액 출력
cout << result;
exit(0);
} // 임시 상한액 < 바로 앞의 금액 -> cur--;
}
// cur가 0까지 이동한 경우 (종료 조건 2)
cout << m / n;
exit(0);
}
}
// 다 더해도 m을 넘지 않으면
// 마지막 원소 자체가 상한액 (종료 조건 3)
cout << arr[n - 1];
return 0;
}
위의 코드는 최악의 경우 시간복잡도가 O(N^2)인데, N이 최대 1만이므로 N^2 = 10^8 = 1억이어서 다행히 시간초과가 발생하지 않은 거 같다. 하지만, N의 범위가 더 커지면 시간초과가 발생할 것이다. 따라서, 더 효율적인 풀이를 알아보자!
이진 탐색 : O(NlogN)
https://tooo1.tistory.com/129
https://ongveloper.tistory.com/313
start는 1로, end는 예산요청 중에서 최댓값으로 설정하고, 우리가 구하고자 하는 상한액을 mid라고 하자. (mid는 임시 상한액, 최종 답은 answer)
이후 start, end를 좁혀 나가며 이진 탐색을 진행한다.
임시 상한액 mid를 고려하여 모든 지방에 예산을 배정했을 때, 그 합이 m을 초과하지 않는다면 답을 mid로 갱신하고 상한액의 최댓값을 구하기 위해 mid를 뒤쪽으로 이동시킨다. 만약 그 합이 m을 초과한다면 mid의 위치를 앞쪽으로 이동시켜서 상한액의 값을 줄인다.
재귀적 풀이
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
int arr[10001];
int answer = 0;
int calcBudget(int mid){
int sum = 0;
for(int i = 0; i < n; i++){
// 예산이 상한액보다 크면
if(arr[i] > mid){
// 상한액으로 더하고
sum += mid;
}else{
// 아니면 요청한 예산 그대로 더하기
sum += arr[i];
}
}
return sum;
}
void biSearch(int start, int end){
int mid = (start + end) / 2;
int result = calcBudget(mid);
if(start > end){
return;
}
if(result <= m){
answer = mid;
// 상한액의 최댓값을 구하기 위해 뒤쪽으로 이동
biSearch(mid + 1, end);
}else{
// 상한액을 줄이기 위해 앞쪽으로 이동
biSearch(start, mid - 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
cin >> m;
int end = *max_element(arr, arr + n);
biSearch(1, end);
cout << answer;
return 0;
}반복적 풀이
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
int arr[10001];
int answer = 0;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
cin >> m;
sort(arr, arr + n);
int start = 0;
int end = arr[n - 1];
while(start <= end){
int sum = 0;
int mid = (start + end) / 2;
for(int i = 0; i < n; i++){
sum += min(arr[i], mid);
}
// 예산의 총합이 m을 넘지 않으면
if(sum <= m){
answer = mid; // 정답 갱신
// 상한액의 최댓값을 구하기 위해 뒤쪽으로 이동
start = mid + 1;
}else{
// 상한액을 줄이기 위해 앞쪽으로 이동
end = mid - 1;
}
}
cout << answer;
return 0;
}
이진 탐색을 이용한 풀이는 최악의 경우에도 시간복잡도 O(N*logN)을 보장할 것으로 보인다. 실제 실행 시간을 보면 확실히 줄어들었다!
이진 탐색에서 중요한 것은 기준이라고 한다. index를 기준으로 탐색할지, value를 기준으로 탐색할지 문제를 보고 결정해야 한다. 이 문제는 value를 기준으로 이진 탐색하는 문제였다.
기준을 잡았다면, 시작 값과 끝 값을 정해주는 것도 굉장히 중요하다.
이 문제에서 시작 값은 0, 끝 값은 예산 요청에서 가장 큰 값으로 설정했다.
이진 탐색이 시간복잡도를 줄여주는 유용한 도구로 사용될 수 있다는 걸 이 문제를 통해 배웠다! 다음에는 스스로의 힘으로 이진 탐색 아이디어를 떠올릴 수 있기를..!!
