기지국 설치

programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

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

int solution(int n, vector<int> stations, int w)
{
    
    int answer = 3;
    
    int cnt=0;
    int sz = w+w+1;
    int si =0;
    for(int i=1; i<=n; i++){
        
        
       if(i>=stations[si]-w && i<=stations[si]+w){
           
           i=stations[si]+w; 
           si++;
           
        }
        else{
            i=i+sz-1;
            cnt++;
            if(i>n){break;}
            
    }

    }
    answer = cnt; 
    return answer;
}

 

- 효율적인 탐색 법에 대해 알 수 있다. 

- 이미 설치된 구간과 이미 설치되지 않은 구간 을 나누어서 생각을 해주어야한다.