2110 공유기 설치

와우

어려웠다

뭔가 범위로 어찌저찌 해야한다는 느낌은 왔는데 느낌만 오고 어떻게 다뤄야할지 모르겠다. 그래서 결국 도움 받아서 풀었다.

 

먼저 범위 기준을 가장 인접한 길이로 잡고 그 길이에 맞춰 반씩 범위를 줄인다. 

범위를 확인하는 함수는 일정한 길이가 주어질 때 공유기 갯수로 확인한다. 공유기 갯수가 C개 이상이라면 그 길이가 적당한거고 갯수가 C개 미만이라면 길이가 너무 길다는 것이다. 

 

코드는 이렇게 짰다. 여기서 다 int형으로 했는데 나중에 문제 확인해보니 터질 것 같아서 long long으로 바꿔줬다.  그리고 count도 0으로 했는데 항상 맨 처음거에 공유기를 두기 때문에 count를 1로 뒀다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool check(int mid, int c, vector<i64> v){
    int count = 1;
    i64 before = v[0];
    
    for(int i = 1; i < v.size(); i++){
        if(v[i] - before >= mid){
            count++;
            before = v[i];
        }
    }
    if(count >= c)
        return true;
    return false;
}

int main() {
    int n, c;
    scanf("%d %d", &n, &c);
    vector<i64> v(n);
    
    for(int i = 0; i < n; i++)
        scanf("%lld", &v[i]);
    sort(v.begin(), v.end());
    
    i64 low = 1;
    i64 high = v[n-1] - v[0] + 1;
    
    while(true){
        if(low == high - 1)
            break;
        i64 mid = (low + high)/2;
        
        if(check(mid, c, v))
            low = mid;
        else
            high = mid;
    }
    
    printf("%lld", low);
    
}

 

맞았다...! 또 틀릴 줄 알았는데 맞아서 먼가 싱숭생숭,, 실력이 좀 쌓였으면 좋겠다.