[프로그래머스 - C++] 기지국 설치

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

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

 

풀이

이 문제는 재귀를 사용해서 풀이하였습니다.

우선 이미 있는 기지국을 가지고 전파가 전달되지 않는 구간들만 찾아서 해당 구간들에 대해 sol()함수를 호출합니다.

sol()함수 내에서는 하나의 기지국을 앞에서 부터 설치하고 뒤에 아직도 전파 전달이 되지 않는 구간이 있을 경우 그 구간에 대해 sol()함수를 다시 호출합니다.

 

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

int cnt = 0;

void sol(int start, int last, int w){
    cnt++;
    if(last - start > w*2){
        start = start+w*2+1;
        sol(start, last, w);
    }
}

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    sort(stations.begin(), stations.end());
    int start = 1, last = 1;

    int sSize = stations.size();
    for(int i=0; i<sSize; i++){
        if(i==0){
            start = 1;
            last = stations[i]-w-1;
            if(start>last)
                continue;
            sol(start, last, w);
        }
        else {
            start = stations[i-1]+w+1;
            last = stations[i]-w-1;
            if(start>last)
                continue;
            sol(start, last, w);
            
        }
    }
    //마지막
    start = stations[sSize-1]+w+1;
    last = n;
    if(start<=last)
        sol(start, last, w);
    
    answer = cnt;

    return answer;
}