(C++) - 백준(BOJ) 13702번 : 이상한 술집

https://www.acmicpc.net/problem/13702

13702번: 이상한 술집

이분탐색(Binary Search)문제입니다.

개인적으로 변수 l은 1과 무척 헷갈리므로 대문자 L로 사용하심을 추천합니다. 저거 하나 때문에 뇌핏줄에 심각한 손상이 올 수 있습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. n, k를 입력받습니다. 각각 주전자 개수, 친구들의 수 입니다.

 

 2. n만큼 loop를 돌며 주전자의 용량을 입력받습니다. 입력받을 때마다 a배열에 저장해줍니다. 그리고 big에 a의 최댓값을 저장해줍니다.

 

📔 풀이과정

1을 l, r을 big으로 정합니다. 찾으려는 값은 일정량 나눠줄 적절한 주전자의 용량입니다. 이를 mid로 두어 배분해봤을 때 cnt명이 되는 값을 찾아 ans에 저장합니다.

 

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <iostream>
using namespace std;
long long n, k,a[10000], r, l, mid, big, cnt, ans;
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (big < a[i])
            big = a[i];
    }
    l = 1;
    r = big;
    while (l<=r)
    {
        cnt = 0;
        mid = (l + r) / 2;
        for (int i = 0; i < n; i++)
            cnt += a[i] / mid;
        if (cnt >= k)//배분량을 늘려야 cnt가 감소
        {
            if (ans < mid)
                ans = mid;
            l = mid + 1;
        }
        else //cnt가 작을 때
            r = mid - 1;
    }
    cout << ans << '\n';
}