[백준OJ] 6209번 제자리 멀리뛰기

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

6209번: 제자리 멀리뛰기

---

 

풀이

https://khu98.tistory.com/257

[프로그래머스] 징검다리

위의 문제와 같은 로직의 문제이다.

먼저 돌들이 순서대로 들어왔다는 보장이 없으므로, 정렬을 해준뒤, 마지막 도착지점도 돌을 놔준다.

그다음 이분탐색의 mid값을 돌다리 사이의 최소거리라고 생각을 하고, 돌들을 탐색하면서 이 최소거리로 건너뛸 수 있는 돌들을 체크해준다. 이 돌들이 제거하려는 돌보다 많다면, 간격을 줄이기 위해 right의 값을 갱신시켜주고, 돌들이 제거하려는 돌보다 적거나 같다면, 간격을 늘려주기 위해 left값을 갱신시켜주면된다.

 

시간복잡도

정렬에 O(NlogN)시간이 걸리며, 이분탐색으로 O(NlogN)이 걸리므로, 총 O(NlogN)이 된다

 

코드

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> maze;
int n,m,d;

int main() {
    cin>>d>>n>>m;
    
    for(int i=0;i<n;i++){
        int data;
        cin>>data;
        maze.push_back(data);
    }
    int left=0;
    int right=d;
    int ret;
    maze.push_back(0);
    maze.push_back(d);
    sort(maze.begin(),maze.end());
    
    while(left<=right){
        int mid=(left+right)>>1;
        int sum=0;
        int now=0;
        for(int i=1;i<maze.size();i++){
            if(maze[i]-maze[now]<mid){
                sum++;
            }
            else{
                now=i;
            }
        }
        if(sum>m){
            right=mid-1;
        }
        else{
            ret=mid;
            left=mid+1;
        }
    }
    cout<<ret;
	return 0;
}