[틀림] 프로그래머스 징검다리 // 매개변수 탐색

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

* 풀이

• 완탐 -> 50000Cn -> 불가

• 매개변수 탐색
  • f(x) : 최소거리가 x일때, 제거대상 바위수가 n 이하인가?
  • prev 변수가 킥이다.

#include <bits/stdc++.h>

using namespace std;

int ret,n; 
int dist;
vector<int> rocks;
int go(int x){
    int cnt=0;
    int prev=0; //이전위치
    for(auto rock : rocks){
        //제거대상
        if(abs(prev-rock) < x){
            cnt++;
        }
        else{
            prev=rock;
        }
    }
    
    //마지막 처리
    if(abs(prev-dist) < x){
        cnt++;
    }
    
    return cnt <=n;
    
}

int solution(int _distance, vector<int> _rocks, int _n) {
    dist=_distance;
    rocks=_rocks;
    n=_n;
    
    sort(rocks.begin(),rocks.end());
    
    int st=1;
    int en=1000000000;
    while(st<=en){
        int mid = (st+en)/2;
        if(go(mid)){
            ret=mid;
            st=mid+1;
        }
        else{
            en=mid-1;
        }
    }
    return ret;
}

 

* 의문

• 문제에서 바위 n개를 제거해야한다고 했는데
• cnt <= n 했는데 정답인이유?
  • 그때의 x는 ret 후보임
  • 딱 n개 사용일수도 있고 n개 미만일수도 있음 
  • but
  • 더 작은 x를 찾아서 탐색하니까
  • 더작은 x가 있다면 그게 답이 될것이기 때문.