[백준] 13702번 이상한 술집 (C++)

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

 

 

이 문제는 N개의 랜덤으로 할당되는 막걸리의 개수가 주어지고 K명이 주어진 후 랜덤 막걸리의 용량이 주어진다.

이때 K명에게 똑같은 용량으로 막걸리를 나눠준다고 했을때 최대한 많은 막걸리의 용량을 주려하기 때문에

 

최대한의 용량으로 K명에게 똑같이 나눠줄 수 있는 막걸리의 양을 구해야 한다.

 

막걸리의 개수는 최대 1만개 이며 랜덤 막걸리의 용량은 100만이다

무지성 완전탐색을 한다면 시간복잡도는 O(NK)로 1억을 가뿐하게 넘길 것이다.

 

 

나의 전략은 이분탐색을 사용하는 것이다. 막걸리의 용량을 이분탐색 범위로 설정한 후 

K만큼 나눠줄 수 있는 경우 막걸리의 최대용량을 주는것이기 때문에 왼쪽 포인터를 땡겨서 막걸리를 줄 수 있는 최대용량을 높이며

K만큼 못나눠 줄 경우 무조건 나눠줘야 하기 때문에 오른쪽 포인터를 땡겨 막걸리의 용량을 줄이는 방식을 사용하였다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
ll N, K, answer;
vector<int> v;

void solve() {
    ll start = 1;
    ll end = 1e18;

    while(start <= end) {
        ll mid = (start + end) / 2;

        int cnt = 0;
        for(int i = 0; i < N; i++) {
            int div = v[i] / mid;
            cnt += div;
        }

        if(cnt >= K) {      // 더 늘려야함
            start = mid + 1;
            answer = mid;
        }
        else {
            end = mid - 1;
        }
    }

    cout << answer;
}

void input() {
    cin >> N >> K;

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

solve함수를 살펴보면

void solve() {
    ll start = 1;
    ll end = 1e18;

    while(start <= end) {
        ll mid = (start + end) / 2;

        int cnt = 0;
        for(int i = 0; i < N; i++) {
            int div = v[i] / mid;
            cnt += div;
        }

        if(cnt >= K) {      // 더 늘려야함
            start = mid + 1;
            answer = mid;
        }
        else {
            end = mid - 1;
        }
    }

    cout << answer;
}

 

왼쪽 포인터는 1로 설정하였고 오른쪽 포인터는 long long 범위의 가장 큰 값을 사용하였다.

이때 mid값이 나눠줄 막걸리 용량 값이며 위에 설명했던대로 포인터를 옮기는 방법을 사용했다.