문제 개요
이 문제에서는 크기가 n인 배열 arr[]와 숫자 S가 주어지며, 우리의 목표는 수정된 배열의 최솟값이 가질 수 있는 최댓값을 찾는 것입니다.
배열을 수정할 때 지켜야 할 규칙은 다음과 같습니다.
수정 전 배열 요소들의 합과 수정 후 합의 차이는 정확히 S여야 합니다.
수정된 배열에는 음수 값이 허용되지 않습니다.
수정된 배열의 최솟값은 가능한 한 커야 합니다(최대화).
배열의 수정은 임의의 요소를 늘리거나 줄이는 방식으로 수행할 수 있습니다.
이러한 제약 조건 안에서 새로운 배열을 구성하고, 배열에서 가장 작은 요소의 최댓값을 반환해야 합니다.
예제를 통해 문제를 살펴보겠습니다.
입력 : arr[] = {4, 5, 6}, S = 2
출력 : 4설명
원래 배열의 합은 15입니다. 각 요소가 최소 4 이상이 되도록 유지하면서 합을 정확히 2만큼 줄인 수정된 배열은 {4, 4, 5}가 될 수 있으며, 이때의 최솟값인 4가 우리가 구하려는 답입니다.
풀이 접근 방식
핵심은 수정된 배열의 최솟값을 최대화하는 것입니다. 가능한 최솟값의 범위는 0(가능한 최솟값)부터 arrmin(배열의 최솟값, 가능한 최댓값)까지이므로, 이 범위에서 이진 탐색(binary search)으로 최적의 값을 찾습니다. 각 후보 값 mid에 대해 "모든 요소를 최소 mid 이상으로 만들었을 때 줄일 수 있는 총합(arrSum − mid × n)이 S 이상인지"를 검사하며 탐색 범위를 좁혀 나갑니다.
또한 다음과 같은 특수 조건을 먼저 처리해야 합니다.
S가 배열 전체 합보다 크면 어떻게 수정해도 조건을 만족할 수 없으므로 해가 존재하지 않습니다(-1 반환).
S가 배열 전체 합과 같으면 모든 요소를 0으로 만들어야 하므로 최솟값은 0이 됩니다.
구현 예제
다음 프로그램은 위 접근 방식이 실제로 동작하는 모습을 보여줍니다.
#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
int minVal = a[0];
int arrSum = a[0];
for (int i = 1; i < n; i++) {
arrSum += a[i];
minVal = min(a[i], minVal);
}
if (arrSum < S)
return -1;
if (arrSum == S)
return 0;
int s = 0;
int e = minVal;
int ans;
while (s <= e) {
int mid = (s + e) / 2;
if (arrSum - (mid * n) >= S) {
ans = mid;
s = mid + 1;
}
else
e = mid - 1;
}
return ans;
}
int main(){
int a[] = { 4, 5, 6 };
int S = 2;
int n = sizeof(a) / sizeof(a[0]);
cout<<"수정된 배열의 최솟값의 최댓값은 "<<findmaximisedMin(a, n, S);
return 0;
}출력
수정된 배열의 최솟값의 최댓값은 4
복잡도 분석
시간 복잡도: O(n × log(arrmin)) — 배열의 합과 최솟값을 구하는 데 O(n), 이진 탐색에 O(log(arrmin))이 소요됩니다.
공간 복잡도: O(1) — 추가적인 자료 구조를 사용하지 않습니다.