Programmers - 기지국 설치

---

title: Programmers - 기지국 설치
date: 2022-08-19
tags:

• Algorithm
• Greedy

---

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

문제 요약

N개의 아파트가 일렬로 나열되어 있으며, 몇몇 위치에는 기지국이 설치되어 있다.
각 기지국은 좌우로 W만큼 전파를 전달하며, 모든 아파트에 전파가 전달될 수 있도록 설치할 최소의 기지국 개수를 return한다.

문제 풀이

Greedy하게 풀면 되는 문제이다.
앞에서부터 최소한의 설치를 통해 전력을 전달해나간다. 일부 위치를 뒤에서 전달하기 위하여 빼놓을 수 있으나, 이 경우 동일한 기지국을 설치함에도 전달 가능한 범위가 줄어든다.
최대 200M의 아파트가 존재한다. 각 아파트를 하나하나 검사하면 O(n)의 시간 내에 해결할 수 있으나 최대 200M의 loop를 시행한다.
이에 반해 기존에 설치된 기지국은 최대 10K로, 이 기지국을 이용하여 검사하면 동일한 O(n)의 시간 내에 해결할 수 있으나 최대 10K의 loop로 더욱 효율적이다.


이전까지 설치된 기지국을 통해 n번째 아파트까지는 전력 전달이 완료된 상황이라고 하자.
n+1번째 아파트부터 다음 기지국이 좌측으로 전달하지 못하는 아파트의 개수를 확인한다.
Ceiling function을 이용하는 것이지만, 대신 1을 뺀 뒤 나눈 후, 마지막에 1을 더해주는 것도 동일한 동작을 한다.
사이의 아파트 개수를 통해 해당 구간에서 최소로 설치할 기지국의 개수를 더해준다. 다음 위치는 현재 이용한 기존의 기지국이 우측으로 전달하는 아파트의 끝이다.
마지막 loop 이후 최우측 아파트에 전력이 전달이 되지 않을 수 있으므로 추가적인 처리를 1회 해준다.


최대 약 0.1ms의 좋은 성능으로 문제를 해결하였다.

프로그램

#include <vector>

using std :: vector ;

int solution ( int n , vector < int > stations , int w )
{
    int answer = 0 ;
    int iElectricityEndIndex = 1 ;
    int iStationSize = stations.size () ;



    for ( int i = 0 ; i < iStationSize ; ++i  )
    {
        if ( iElectricityEndIndex < stations [ i ] - w )
        {
            int iGap = stations [ i ] - w - iElectricityEndIndex ;
            int iQuotient = ( iGap - 1 ) / ( ( w << 1 ) + 1 ) + 1 ;
            answer += iQuotient ;
        }

        iElectricityEndIndex = stations [ i ] + w + 1 ;
    }

    if ( iElectricityEndIndex <= n )
    {
        answer += ( n - iElectricityEndIndex ) / ( ( w << 1 ) + 1 ) + 1 ;
    }


    return answer ;
}