프로그래머스 : 기지국 설치 C++

programmers.co.kr/learn/courses/30/lessons/12979?language=cpp

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

풀이 및 후기

1. 난 진짜 빡구현보다 이런게 더 어렵다, 아무리 문제를 풀어도 왜 생각이 안날까

 

1) index 두개로 관리한다

 - station, 오름차순으로 정렬되어 있다

 - now, 지금 내 위치!

 

2) now가 n까지 갈때까지 while 루프

 

 지금 위치에 전파가 안온다면 기지국 설치

  -> 지금 위치를 왼쪽끝에 걸치게 설치하는거니까 now += w*2

  -> answer++;

 지금 위치가 전파 오는 곳이라면, 지금 속해있는 전파 위치 오른쪽 끝으로

 

 다음 칸 이동

 

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



int solution(int n, vector<int> stations, int w)
{
    int answer=0;
    int now =1;
    int station_index =0;
    while(now<=n)
    {
        //현재 위치가 범위 안이라면
        if(now >= stations[station_index]-w && now <= stations[station_index]+w)
        {
            now = stations[station_index]+w;
            station_index++;
        }
        else//기지국 새로 설치!
        {
            answer++;
            now += w*2;
        }
        //다음칸으로~
        now++;
    }
    
    return answer;
}