프로그래머스 - 기지국 설치

문제

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

프로그래머스

최소한의 기지국을 설치하는 문제였다.

 

문제 풀이

처음에는 각 기지국의 전파 범위를 start와 end로 계산해 pair 벡터에 저장하게 해서 문제를 풀었는데 4개의 테스트케이스에서 틀렸고 수정하기가 애매하고 코드도 지저분해서 다시 풀었다. pair 벡터에 저장하지 않고 i의 값을 옮겨주며 풀었다.

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;    
    int dist;    
    int wdist = w*2 + 1;    
    
    int j=0;
    int start, end;
    for(int i=1;i<=n;i++){
        dist = 0;      
        if( j >= stations.size()){ //마지막
            start = n;
            end = n;
            if(i == start) dist = 1;
        }
        else{
            start = stations[j]-w;
            end = stations[j]+w;
        }
        if(i < start){
            dist = start - i;
        }
        
        //계산
        if(dist != 0){
            answer+= (dist/wdist);
            if(dist%wdist!=0) answer++;        
        }
        
        i = end;
        j++;
    }
    
    return answer;
}