정수 배열 nums와 임계값을 나타내는 정수 k가 주어졌다고 가정해 봅시다. 우리는 양의 정수인 제수(divisor)를 하나 선택하여 배열의 모든 원소를 이 값으로 나눈 뒤, 나눈 결과들을 모두 더해야 합니다. 이때 구해야 하는 것은 그 합이 임계값 k 이하가 되도록 만드는 가장 작은 제수입니다.
예를 들어 nums = [1,2,5,9]이고 k = 6이라면 출력은 5가 됩니다. 제수가 1일 때 합은 (1+2+5+9) = 17이며, 제수가 4일 때는 (1+1+2+3) = 7, 제수가 5일 때는 (1+1+1+2) = 5가 됩니다. 따라서 조건을 만족하는 가장 작은 제수는 5입니다.
참고로, 문제에서는 반드시 답이 존재함이 보장됩니다.
접근 방법: 이진 탐색(Binary Search)
핵심 아이디어는 다음과 같습니다. 제수가 커질수록 각 원소를 나눈 올림 값은 작아지거나 그대로이므로, 전체 합은 단조 감소(monotonically decreasing)하는 성질을 가집니다. 이러한 단조성 덕분에 선형 탐색 대신 이진 탐색을 사용하여 시간 복잡도 O(n log M)(M은 최대 제수 범위)만에 답을 효율적으로 구할 수 있습니다.
풀이 단계
- 검증용 메서드 ok(x, nums, th)를 정의합니다. 이 메서드는 제수 x로 나눴을 때의 합이 임계값 이하인지 판별합니다.
- sum := 0 으로 초기화
- 배열 전체를 순회하면서 sum += ceil(nums[i] / x) 누적
- sum <= th 이면 true, 아니면 false 반환
- 실제 탐색 메서드의 흐름은 다음과 같습니다.
- low := 1, high := 충분히 큰 값(예: 10^7)으로 설정
- low < high 인 동안 반복:
- mid := low + (high - low) / 2
- ok(mid)가 true이면 high := mid (더 작은 제수 탐색), 아니면 low := mid + 1
- 반복 종료 후 high 값을 반환
구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(int x, vector <int> &nums, int th){
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += ceil((double)nums[i]/(double)x);
}
return sum<=th;
}
int smallestDivisor(vector<int>& nums, int th) {
int low = 1;
int high = 1e7;
while(low < high){
int mid = low + (high - low)/2;
if(ok(mid, nums, th)){
high = mid;
}else low = mid + 1;
}
return high;
}
};
main(){
vector<int> v = {1,2,5,9};
Solution ob;
cout << (ob.smallestDivisor(v, 6));
}입력
[1,2,5,9] 6
출력
5
마무리
이 문제는 "나누는 값이 커지면 결과 합이 줄어든다"는 단조성을 파악하는 것이 관건입니다. 이 성질을 이용해 이진 탐색으로 조건을 만족하는 최솟값을 좁혀 나가면, 배열의 크기나 제수 범위가 커져도 안정적인 성능을 보장할 수 있습니다. 코딩 테스트에서 자주 등장하는 매개변수 탐색(Parametric Search) 유형의 대표적인 예제이므로, 풀이 패턴을 잘 익혀두면 유사한 문제에도 손쉽게 적용할 수 있습니다.