Vic_cinth
2110-공유기 설치

  09 Nov 2019


Problem

Image

Concept & Idea

나무자르기 문제를 내가 직접 풀어냈다는 느낌이 약해서 리뷰를 쓰지 않았다. 이 문제는 이분탐색으로 가장 인접한 두 공유기의 최댓값을 찾는 문제였다. 처음에는 이분탐색으로 설치를 하는 방식을 짜야한다고 생각했고, 어떻게 적절한 위치에 설치를 할지 우선순위를 잡아야하나 고민하였다. 하지만 그 어떤 우선순위에도 확실한 과정이 없어서, 질문검색을 통해 아이디어를 찾았다.

중요한 점은 내가 직접 구간을 설정해서 이 구간이 가능한지 여부를 판단하고, 이분탐색으로 이 구간을 정해나가는 것이다. mid라는 구간만큼 공유기를 설치했을 때, 설치가 가능하면 mid값을 더 키우고 불가능하면 더 줄여서 최적의 값을 이분탐색으로 찾아나가는 것이다. 여기서 가능한지의 여부는 그냥 count를 세면 됬었는데,, 괜히 복잡한 조건을 추가해서 시간초과가 발생한 것 같다.. 파라메트릭 서치에 대해 간단히 공부해보자.

Image 파라메트릭 서치는 바이너리 서치와 비슷하다고 느낄 수 있다. 가장 중요한 것은, 바이너리 서치의 경우 mid값이 일치하는지 여부를 확인하는 것이 매우 중요하다. 파라메트릭 서치에서는 내가 원하는 조건을 가장 만족하는 알맞는 값을 특정한 범위내에서 찾고 싶을 때 그 알맞는 값을 찾을 때 이분탐색이 들어가는 것이다.

최적화 문제(문제의 상황을 만족하는 특정 변수의 최댓값 또는 최솟값)을 결정 문제로 바꾸어 푸는것

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> vec;
int n,c;
long long res=-1;
int main(){
    cin>>n>>c;
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        vec.push_back(a);
    }
    sort(vec.begin(), vec.end());
    long long st=0,en=vec[vec.size()-1];
    long long mid;
    while(st<=en) {
        mid = (st+en)/2;
        int start=vec[0];
        int count=1;
        for(int i=1; i<n; i++) {
            if(start+mid<=vec[i]) {
                count++;
                start=vec[i];
            }
        }
        if(count>=c) {
            res=max(res,mid);
            st=mid+1;
        } else {
            en=mid-1;
        }
    }
    cout<<res<<endl;
}


Fealing

이 문제를 이분탐색으로 어떻게 해결할까 하다가.. 결국 질문검색에서 아이디어를 얻어서 풀게 되었다. 파라메트릭 서치가 뭔지 모르고 풀었다가 친구의 설명을 듣고 아~ 몰라!했었는데, 다시보니까 이게 또 파라메트릭 서치였다니.. 생각을 좀 더 단순히 해서 간단히 해결할 방법을 찾아야겠다..

Check out this code in Victoria’s Gist. Please Comment my code in this link.

...