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

문제 링크

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

 

 

 

풀이

전달되지 않는 범위를 ranges 컨테이너에 담아서 최소 개수를 리턴하여 풀었다.

 

최소 개수만을 리턴하는 문제이므로

전달되지 않는 범위(vector 컨테이너 값) / 전달 범위(2w+1)가 최소 개수고

전달되지 않는 범위(vector 컨테이너 값) % 전달 범위(2w+1)로 나머지가 있다면 기지국 1개를 더 추가해준다.

 

 

 

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

// 아파트 개수 n, 사전 기지국 설치 stations, 범위 w

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    vector<int> ranges;
    
    // 전달되지 않는 범위 담기
    int start=1;
    for(int i=0; i<stations.size(); i++){
        // printf("start(%d)\n", start);
        int fin = stations[i]-w;
        if(fin-start>0){
            ranges.push_back(fin-start);
        }
        start = stations[i]+w+1;
    }
    if(n-start >= 0){
        // printf("start(%d)\n", start);
        ranges.push_back(n-start+1);
    }
    
    // 최소 개수
    int range = w*2 + 1;
    for(auto e: ranges){
        answer += e / range;
        answer += (e%range)!=0 ? 1 : 0;
    }
    
    return answer;
}