[백준/Baekjoon] 13702 이상한 술집 C++ :: Binary search

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

13702번: 이상한 술집

---

1. Logic

막걸리 를 최대한 많이 따를 수 있는 만큼 따르고 나머지는 버린다고 했으니 우리는 K잔을 만들 수 있는 최대 값을 찾아야 한다. 우리가 탐색하는 부분에 대해서 정답은 TTT[TF]FFF 중간 대괄호부분에서 정답이 결정된다. 우리가 구해야 하는 값은 가능한 수들중에서 최댓값이기 때문에 left를 반환하면 된다.

---

2. Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long n, k;

long long maxValue = 0;
long long ans = 0;

vector<long long> drink;

bool check(long long mid) {
    long long cnt = 0;
    for(long long i = 0; i < n; i++) {
        cnt += drink[i] / mid;
    }
    if(cnt >= k) return true;
    else return false;
}

long long binarySearch() {
    long long start = 0;
    long long end = 2147483647;
    long long mid;
    

    while(start + 1 < end) {
        mid = (start + end) / 2;
            
        if(check(mid)) start = mid;
        else end = mid;
    }
    
    return start;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cin.tie(0);
    cin >> n >> k;
    
    for(long long i = 0; i < n; i++) {
        long long a;
        cin >> a;
        maxValue = max(maxValue, a);
        drink.push_back(a);
    }
    
    cout << binarySearch();
}

 

---

3. Feedback

이분탐색 알것같아..!

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90