문제 개요
n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 배열의 모든 요소를 특정 값 x로 통일했을 때(arr[i] = x), 새 배열 전체의 곱이 원래 배열 전체의 곱보다 엄격하게 커지도록 만드는 최솟값 x를 구하는 것이 목표입니다.
제약 조건은 다음과 같습니다.
- 1 ≤ n ≤ 10^5
- 1 ≤ arr[i] ≤ 10^10
예를 들어 배열이 [4, 2, 1, 10, 6]이라면 정답은 4입니다. 4 × 4 × 4 × 4 × 4 = 1024로, 원래 곱인 4 × 2 × 1 × 10 × 6 = 480보다 크기 때문입니다. 반면 3으로 채우면 3⁵ = 243으로 조건을 만족하지 못합니다.
접근 방법: 로그 활용
요소 값이 최대 10^10이고 n이 최대 10^5이므로, 실제 곱을 직접 계산하면 오버플로우가 발생합니다. 이때 로그를 사용하면 문제를 효율적으로 해결할 수 있습니다.
n개 요소의 곱을 P라 할 때, 필요한 값은 사실상 P의 n제곱근입니다. 로그의 성질을 이용하면 다음과 같이 계산할 수 있습니다.
res = ceil(10 ^ ((log a₁ + log a₂ + ... + log aₙ) / n))
즉, 각 요소의 로그 값을 모두 더한 뒤 n으로 나누고, 역로그(antilog)를 취한 결과를 올림(ceil)하면 정답이 됩니다.
C++ 구현 예시
#include <iostream>
#include <cmath>
#define EPS 1e-15
using namespace std;
long long findMinValue(long long arr[], long long n) {
long double sum = 0;
for (int i = 0; i < n; i++)
sum += (long double)log10(arr[i]) + EPS;
long double xl = (long double)(sum / n + EPS);
long double res = pow((long double)10.0, (long double)xl) + EPS;
return (long long)ceil(res + EPS);
}
int main() {
long long arr[] = {4, 2, 1, 10, 6};
long long n = sizeof(arr) / sizeof(arr[0]);
cout << "Min value is: " << findMinValue(arr, n);
}실행 결과
Min value is: 4
코드 설명
- 각 배열 요소에 대해 log10을 계산해 누적합니다. 부동소수점 오차를 보정하기 위해 미세한 값 EPS(1e-15)를 더합니다.
- 누적된 로그 합을 n으로 나눠 평균 로그값을 구합니다.
- 밑이 10인 거듭제곱 연산으로 역로그를 계산합니다.
- ceil 함수로 결과를 올림한 후 long long 형태로 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다. 로그 변환 덕분에 큰 수의 곱셈 오버플로우 없이 안전하게 최솟값을 구할 수 있다는 점이 핵심입니다.