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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 조금만 생각하면 쉽게 풀 수 있는 문제다.

아래 그림을 참고해 보자

 여기서 기지국을 어떻게 설치해야 할까?

이미 설치된 기지국의 범위와 새로 설치하는 기지국의 범위가 같다는 점에 유의하면

기지국을 최소로 설치하기 위해서는 기지국이 설치되지 않은 연속된 칸을 기지국의 범위로 나누면 쉽게 해결할 수 있다. 

 그림에서 보이듯이 기지국을 설치할 때 차지하는 칸의 범위가 3이라면 1~2 범위는 크기가 2이므로 기지국을 하나 설치해서 그 범위를 메꿀 수 있다.

 

다음 범위는 6~9의 범위를 메꿔야 하는데, 범위의 크기가 4이므로 기지국을 2개 설치해야 메꿀 수 있다.

 

이처럼 연속으로 비어있는 부분의 크기를 기지국의 범위로 나눠서 더하면 설치해야하는 최소 기지국의 개수를 구할 수 있다.

 

+ 기지국의 위치가 오름차순으로 정렬되어 있으므로, 이전 기지국의 끝점과 현재 기지국의 시작점의 거리가 연속으로 비어있는 부분의 크기다.

 

 

 

​

[아이디어 정리]

1. 오름차순으로 기지국의 위치가 정렬되어 있으므로, 이를 이용해 기지국의 영향에서 벗어난 부분의 크기를 구한다. 
2. 영향에서 벗어난 부분의 크기를 구했으면, 기지국을 설치했을 때 영향을 주는 범위로 나눈 다음 올림해 더한다.
3. 1, 2번을 반복해 구한 최종 수를 return한다.

 

 

Code

 

 

#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int fa=1+2*w; //기지국을 설치할 때 범위

    int st=1,nextSt; //이전 기지국의 끝, 현재 기지국의 시작점을 저장할 변수
    for (int i=0; i<stations.size(); i++)
    {
        nextSt=stations[i]-w;
        if (nextSt>st)
        {
            answer+=((nextSt-st)/fa) +((nextSt-st)%fa>0?1:0);
        }
        st=stations[i]+w+1;
    }
    if (st<n+1)
    {
        answer+=((n+1-st)/fa) +((n+1-st)%fa>0?1:0);
    }
    return answer;
}

 

---

 

단순히 덧셈과 나눗셈만 잘 하면 되는 쉬운 문제였다.

 

프로그래머스