백준 13702번 이상한 술집

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

이진탐색(Binary Search) 문제였습니다.

막걸리 나누는 양을 1부터 순차적으로 탐색을 진행하는 것보다 이진탐색을 통해 탐색을 진행하면 효율적으로 탐색을 할 수 있습니다.

막걸리를 나눌 수 없는 경우가 있을 수 있기 때문에 low를 0으로 잡았고 막걸리의 용량이 (2^31 - 1) 보다 작다고 했으니 high를 (2 ^ 31 - 1)로 잡은 뒤 이진탐색을 진행했습니다!

overK 함수는 문제에서 K명에게 막걸리를 똑같이 나누라는 요구사항을 충족하는지 판별하는 함수입니다.

#include <iostream>

using namespace std;

 

const int INF = 1 << 31 - 1;

const int MAX = 10000 + 1;

 

int N, K;

int kettle[MAX];

 

//K명 이상 나누어줄 수 있는가?

bool overK(int amount)

{

        int cnt = 0;

 

        for (int i = 1; i <= N; i++)

        {

                 cnt += kettle[i] / amount;

                 if (cnt >= K)

                         return true;

        }

        return false;

}

 

//이분탐색

int binarySearch(void)

{

        int low = 0, high = INF;

 

        while (high >= low)

        {

                 int mid = (low + high) / 2;

                

                 //조건에 부합한다면

                 if (overK(mid))

                         low = mid + 1;

                 else

                         high = mid - 1;

        }

        return high;

}

 

int main(void)

{

        cin >> N >> K;

       

        for (int i = 1; i <= N; i++)

                 cin >> kettle[i];

 

        int result = binarySearch();

        if (result == -1)

                 cout << 0 << endl;

        else

                 cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

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