parametric search 알고리즘

- 해를 바로 구해내는 것이 아니고, 임의의 값을 던지고 맞는지 확인해가며 해를 구하는 방법

- 길이가 다른 K개의 리본, N개의 리본재료를 만드려 함. 리본 재료의 최대 길이를 구하시오

#include <stdio.h>

#define MAX_RIBBON 100

int K;
int N;
int low, high, mid, numRibbonTape, max;
int sizeRibbonTape[MAX_RIBBON];

void search()
{
    mid = low + (high - low) / 2;
    numRibbonTape = 0;

    for (int i = 0; i < K; i++)
    {
        numRibbonTape += (sizeRibbonTape[i] / mid);
    }

    if (numRibbonTape >= N)
    {
        low = mid + 1;
        if (max < mid)
            max = mid;
    }
    else
    {
        high = mid - 1;
    }
}

int main(int argc, char** argv)
{
    int T;
    scanf("%d", &T);

    for (int test_case = 1; test_case <= T; test_case++)
    {
        low = 1;
        high = 0;
        max = -1;

        scanf("%d %d", &K, &N);

        for (int i = 0; i < K; i++)
        {
            scanf("%d", &sizeRibbonTape[i]);
            if (high < sizeRibbonTape[i])
            {
                high = sizeRibbonTape[i];
            }
        }

        while (low <= high)
        {
            search();
        }
        printf("#%d ", test_case);
        printf("%d\n", max);
    }
    return 0;
}