문제

문제 링크

어떻게 접근할 것인가

  • 어떻게 문제를 풀지 고민을 잔뜩하다가 이분탐색을 쓸 수 있는 방법 조차 떠오르는데 진짜 오래걸렸다.
  • 이것은 이분탐색으로 접근하려면 아래의 경우로 탐색을 진행해야 한다.
  • 최대간격을 기준으로 탐색을 진행하면서 몇개의 공유기가 설치될 수 있는지 c와 비교한다.
  • 이 문제는 공유기를 c개 설치할 수 있는 애들 중에 제일 큰 값을 가져와야 하기 때문에 upper_bound를 찾는 것으로 접근해야한다.

upper_bound 찾아주기

  • 기존의 이분탐색 방법처럼 찾는 값과 같다면 리턴해주는 것이 아니라 같더라도 그냥 left가 right를 넘어설때까지 계속 확인해주면서
  • 계속해서 answer을 업데이트 해준다.

함수활용 코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

char in[20000000];
const char* o;

void getIn() {
    o = in;
    in[fread(in, 1, sizeof(in) - 4, stdin)] = '\n';
}

int nextInt() {
    int ret = 0;
    while (*o < '0' || *o > '9') ++o;
    while (*o >= '0' && *o <= '9') ret = 10 * ret + *o++ - '0';
    return ret;
}

int answer;

int binarySearch(vector<int> &v, int l, int r, int c, int n){
    int t, p, mid;
    if(r >= l){
        mid = (l + r) / 2;
        p = 0, t = 1;
        for(int i = 1; i < n; i++){
            if(v[i] - v[p] >= mid){
                t ++;
                p = i;
            }
        }
        if(t >= c) {
            answer = mid;
            return binarySearch(v, mid + 1, r, c, n);
        }
        else return binarySearch(v, l, mid - 1, c, n);  
    }
    return -1;
}

int main(){
    getIn();
    int n, c;
    n = nextInt(), c = nextInt();
    vector<int> v(n);
    for(int i = 0; i < n; i++) v[i] = nextInt();
    sort(v.begin(), v.end());
    binarySearch(v, 1, v[n-1]-v[0], c, n);
    printf("%d", answer);
}

메인함수에서 끝낸 코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

char in[20000000];
const char* o;

void getIn() {
    o = in;
    in[fread(in, 1, sizeof(in) - 4, stdin)] = '\n';
}

int nextInt() {
    int ret = 0;
    while (*o < '0' || *o > '9') ++o;
    while (*o >= '0' && *o <= '9') ret = 10 * ret + *o++ - '0';
    return ret;
}

int main(){
    getIn();
    int n, c, r, l, answer;
    n = nextInt(), c = nextInt();
    vector<int>v(n);
    for(int i = 0; i < n; i++) v[i] = nextInt();
    sort(v.begin(), v.end());
    l = 1, r = v[n - 1] - v[0];
    while(r >= l){
        int mid = (l + r) / 2;
        int p = 0, t = 1;
        for(int i = 1; i < n; i++){
            if(v[i] - v[p] >= mid){
                t ++;
                p = i;
            }
        }
        if(t >= c){            
            answer = mid;
            l = mid + 1;
        } 
        else r = mid - 1;  
    }
    printf("%d", answer);
}

복기 후 결과

사진

느낀점

  • 이분탐색을 정말 이분탐색 답게 푼 것은 이번이 처음인 것 같다.
  • 매우 만족스럽다 ㅎㅎㅎ 다음 문제도 화이팅이이잉~!