[SAP/C++] Smallest Divisor

 

leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

Find the Smallest Divisor Given a Threshold - LeetCode

 

일단 문제를 이해하는 데 좀 걸렸다

나는 divisor라고 하길래, 약수인줄 알았는데 약수가 아니라 그냥..나누는 수 라는 의미였다

 

문제를 정의하면 다음과 같다.

input : 2개 ( integer가 적힌 array , threshold ) 를 받는다.


output : positive divisor이다. 



이 positivie division에는 조건이 있는데, 

array에 존재하는 모든 수를 이 positive division으로 나누어 나오는 몫( 이때 몫은 가우스값으로, 결과 값보다 크거나 같은 integer로 치환하여 생각한다)을 전부 더한값이 threshold를 초과하지 않는 범위에서 가장 큰 수 여야한다

 

어떻게 해야할지 몰라서 일단 Hint를 봤는데, 

Brute - Force 방법으로 해결하는 방법 뿐이라고 한다.

즉, positive divisor를 1부터 시작하여, 하나씩 증가시키면서 계산하여 전부 합한 값이 threshold를 초과하면,

초과하기 직전 postivie division의 값이 답이라는 것.

 

하지만, 이 방법은 너무 시간이 오래걸리기 때문에, 다음과 같이 Binary search를 결합하면, 시간을 줄일 수 있다. 

 

 

답)

//
// Created by 이유정 on 2021/04/21.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

//sum을 계산해서 반환하는 함수
long computeSum(vector<int> nums, int x) {
    long s = 0;
    for (int i = 0; i < nums.size(); i++) {
        s += nums[i] / x + (nums[i] % x == 0 ? 0 : 1);
    }

    return s;
}


int smallestDivisor(vector<int> nums, int threshold) {

    //
    int left = 1;
    int right = 2;

    //threshold를 넘게되는 sum이 존재하는 (divisor) 구간을 찾음
    while (computeSum(nums, right) > threshold) {
        left = right;
        right = right * 2; //구간을 2배씩 늘려가며... divisor가 될수있는 것들 (left~right)
    }

    //찾아내면 그 구간내 어떤 수가 최대인 divisor인지 Binary search를 이용해 찾아냄
    while (left <= right) {
        int pivot = left + ((right - left) >> 1);
        long num = computeSum(nums, pivot);

        if (num > threshold) {
            left = pivot + 1;
        } else {
            right = pivot - 1;
        }
    }

    return left;
}

int main() {
    vector<int> array;
    int threshold;
    int num; // array 요소 수
    int n;

    cin >> threshold;
    cin >> num;
    //array 채우기
    for (int i = 0; i < num; i++) {
        cin >> n;
        array.push_back(n);
    }
    cout << smallestDivisor(array, threshold);

    return 0;

}