백준 2792번 보석 상자

문제 링크입니다: https://www.acmicpc.net/problem/2792

전형적인 이분 탐색 문제였습니다.

해당 길이(mid)로 N명 이하의 사람들에게 나누어줄 수 있는지를 판별해주면 되는 문제였습니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <climits>

using namespace std;

 

const int MAX = 300000;

 

int N, M;

long long jewelry[MAX];

 

//해당 길이로

bool func(long long mid)

{

        long long num = 0;

        for (int i = 0; i < M; i++)

        {

                 num += jewelry[i] / mid;

                 if (jewelry[i] % mid)

                         num++;

        }

        //N명 이하로 나누어줄 수 있는지

        return N >= num;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        long long low = 1, high = 0;

        for (int i = 0; i < M; i++)

        {

                 cin >> jewelry[i];

 

                 high = max(high, jewelry[i]);

        }

 

        long long result = LLONG_MAX;

        while (low <= high)

        {

                 long long mid = (low + high) / 2;

                 if (func(mid))

                 {

                         result = min(result, mid);

                         high = mid - 1;

                 }

                 else

                         low = mid + 1;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~