[ 프로그래머스 기지국 설치 (Lv3) ] (C++)

프로그래머스의 기지국 설치(Lv3) 문제이다.

 

[ 문제풀이 ]

기존에 설치되어 있는 기지국들이 주어지고 기지국의 전파 범위가 주어질 때, 모든 아파트에 전파를 전달하기 위해서 설치해야 하는 기지국들의 최소 갯수를 구해야 하는 문제이다.

기본적으로 전파범위에 따른 기지국 설치 갯수를 구하는 방법부터 정답을 도출하는 과정까지 순차적으로 진행해보자.

 

#1. 전파범위에 따른 커버 영역

가장 먼저 전파범위(w)가 '1'인 경우를 한번 생각을 해보자.

위의 그림과 같이 전파범위가 1인 기지국이 커버할 수 있는 아파트의 갯수는 총 3개가 된다.

그럼 전파범위가 '2'인 경우를 생각을 해보자.

위의 그림과 같이 전파범위가 2인 기지국이 커버할 수 있는 아파트의 갯수는 총 5개가 된다.

그럼 전파 범위가 w인 기지국의 경우 커버할 수 있는 아파트의 갯수는 몇개가 될까 ??

전파 범위가 1인 경우 : 3개

전파 범위가 2인 경우 : 5개

전파 범위가 w인 경우 : ?개

전파 범위가 w인 기지국의 경우, 커버할 수 있는 아파트의 갯수는 W * 2 + 1 개가 된다.

위의 식이 맞는지 확인을 한번 해보자.

전파 범위가 1인경우, 커버할 수 있는 아파트의 갯수는 1 * 2 + 1 = 3 개가 된다.

전파 범위가 2인경우, 커버할 수 있는 아파트의 갯수는 2 * 2 + 1 = 5 개가 된다.

[ 전파 범위가 W인 경우, 커버할 수 있는 아파트의 갯수는 W * 2 + 1 개가 된다 ! ]

 

#2. 커버영역에 따른 설치해야 할 기지국의 갯수

#1에서는 전파 범위가 W인 경우, 몇 개의 아파트 까지 커버를 할 수 있는지에 대해서 이야기 했었다.

그렇다면 이번에는 한 단계 더 나아가서, "K개의 아파트를 커버해야 할 때, 몇 개의 기지국이 필요할까?" 에 대해서 이야기 해보자. 또 예시를 가지고 한번 알아보자. 지금부터 커버 받아야 할 아파트의 갯수가 X개 입니다 라는 표현을 사용할 것인데, 커버 받아야할 아파트들은 모두 연속적으로 존재한다고 가정하겠다.(매우 중요)

 

기지국의 전파 범위(w)가 1일 때, 전파를 받지 못해서 커버 받아야 할 아파트가 1개 인 경우 몇 개의 기지국을 설치해야 할까 ?

이 경우에는 기지국을 1개만 설치해 주면 될 것이다. 커버 받지 못하는 아파트에 기지국을 하나 설치하면 될 것이다.

 

기지국의 전파 범위(w)가 1일 때, 전파를 받지 못해서 커버 받아야 할 아파트가 2개 인 경우 몇 개의 기지국을 설치해야 할까?

이 경우에도 기지국을 1개만 설치해 주면 될 것이다. 왜냐하면 #1에서 이야기했듯이, 전파 범위가 1인 기지국이 커버할 수 있는 아파트의 갯수는 1 * 2 + 1 = 3이 되므로 2개의 아파트는 커버를 할 수 있다.

마찬가지로 전파를 받지 못해서 커버 받아야 할 아파트가 3개인 경우 또한 1개의 기지국만 설치하면 될 것이다.

 

그럼, 기지국의 전파 범위가 1일 때, 전파를 받지 못해서 커버 받아야 할 아파트가 4개인 경우 몇 개의 기지국을 설치해야 할까 ?

딱 봐도 2개라는 것은 쉽게 알 수 있을 것이다. 왜냐하면, 기지국의 전파 범위가 1이라면 기지국이 커버할 수 있는 아파트의 갯수는 3개가 되고, 4개를 커버하기 위해서는 최소 2개가 필요하다는 것을 알 수 있다.

그럼 ! 기지국의 전파 범위가 w일 때, 전파를 받지 못해서 커버 받아야 할 아파트가 K개인 경우 몇 개의 기지국을 설치해야 할까 ?

이렇게 이야기 하면 이해하기 어려우니 위에서 했던 예시들을 정리해보면서 알아보자.

기지국의 전파범위(w) = 1이 주어지면 우리는 이 w값을 통해서 우리는 커버할 수 있는 아파트의 갯수는 1 * 2 + 1 = 3 이라는 것을 알고 있다. 즉 ! 하나의 기지국이 커버할 수 있는 아파트의 갯수가 3개 인 경우...

1. 커버 받아야 할 아파트의 갯수가 1개라면 ? = 설치해야 할 기지국의 갯수는 1개.

2. 커버 받아야 할 아파트의 갯수가 2개라면 ? = 설치해야 할 기지국의 갯수는 1개.

3. 커버 받아야 할 아파트의 갯수가 3개라면 ? = 설치해야 할 기지국의 갯수는 1개.

4. 커버 받아야 할 아파트의 갯수가 4개라면 ? = 설치해야 할 기지국의 갯수는 2개.

 

위의 4가지 예시를 보면서 커버 받아야 할 아파트의 갯수와 설치해야 할 기지국의 갯수간의 관계를 한번 잘 생각해보자.

그리고 다시 이야기해보자. 기지국의 전파 범위가 w일 때, 전파를 받지 못해서 커버 받아야 할 아파트가 K개인 경우 몇 개의 기지국을 설치해야 할까 ??

먼저 ! 기지국의 전파 범위가 w라면, 우리는 하나의 기지국이 커버할 수 있는 아파트의 갯수가 w * 2 + 1 개 라는 것을 알고 있다. 편의상 (w * 2 + 1) 의 값을 'A'라고 표현해보자. w * 2 + 1 = A

하나의 기지국이 커버할 수 있는 아파트의 갯수가 A개 일 때, 커버 받아야 할 아파트의 갯수가 K개라면 설치해야 하는 기지국의 갯수는 ? 바로 (K / A) + 1 개가 된다. 이 식이 맞는지 위의 예시들로 확인 해보자.

하나의 기지국이 커버할 수 있는 아파트의 갯수가 3개 인 경우 (즉, A = 3인 경우)

1. 커버 받아야 할 아파트의 갯수가 1개라면 ? = 설치해야 할 기지국의 갯수는 1개.

- 즉, K = 1 인 경우이다. (K / A) + 1 = (1 / 3) + 1 = 0 + 1 = 1 이 된다.

2. 커버 받아야 할 아파트의 갯수가 2개라면 ? = 설치해야 할 기지국의 갯수는 1개.

- 즉, K = 2 인 경우이다. (K / A) + 1 = (2 / 3) + 1 = 0 + 1 = 1 이 된다.

3. 커버 받아야 할 아파트의 갯수가 3개라면 ? = 설치해야 할 기지국의 갯수는 1개.

- 즉, K = 3 인 경우이다. (K / A) + 1 = (3 / 3) + 1 = 1 + 1 = 2 가 된다.

4. 커버 받아야 할 아파트의 갯수가 4개라면 ? = 설치해야 할 기지국의 갯수는 2개.

- 즉, K = 4 인 경우이다. (K / A) + 1 = (4 / 3) + 1 = 1 + 1 = 2 가 된다.

모든 경우가 맞아 떨어지지만, 유일하게 빨강색으로 표시되어 있는 K = 3인 경우에만 적용이 되질 않는다.

왜 그럴까 ?? 바로 뒤에 붙어있는 '+1' 이 가지는 의미 떄문에 적용이 되질 않는다.

뒤에 있는 '+1' 이 어떤걸 의미할까 ?? 이 수식이 왜 필요할까 ?? K = 4인 경우를 살펴보자.

(4 / 3) + 1 이라는 수식으로 계산을 했는데, 이는, "커버범위가 3인 기지국을 (4 / 3)개 설치한 후에, 그 나머지 부분을 커버하기 위해서 한개를 더 설치하겠습니다." 를 의미한다. 즉, '+1' 이 어떻게 보면 "남은 부분을 커버하기 위해서 붙는 수식" 이라고 생각을 할 수 있다.

K = 1과 K = 2인 경우를 보자. (1 / 3) + 1 과 (2 / 3) + 1은 각각 다음과 같은 의미를 가진다.

K = 1인 경우 : 커버범위가 3인 기지국을 (1 / 3)개 설치한 후에, 즉, 0개를 설치한 후에, 그 나머지 부분(실제로 1/3의 과정에서 0개를 설치하기 때문에 커버해야 할 아파트가 1개가 남아있는 상황)을 커버하기 위해서 한 개를 더 설치하겠습니다.

K = 2인 경우 : 커버범위가 3인 기지국을 (2 / 3)개 설치한 후에, 즉, 0개를 설치한 후에, 그 나머지 부분(실제로 2/3의 과정에서 0개를 설치하기 때문에 커버해야 할 아파트가 2개가 남아있는 상황)을 커버하기 위해서 한 개를 더 설치하겠습니다.

이를 의미하게 된다. 즉 ! '+1'의 수식이 갖는 의미는 위의 내용과 같다.

그렇다면 다시 K = 3인 경우를 살펴보자.

(3 / 3)  + 1 이라는 수식을 이용해서 계산하게 되는데, 이는 커버범위가 3인 기지국을 (3 / 3)개 설치한 후에, 즉, 1개를 설치한 후에, 그 나머지 부분을 커버하기 위해서 한 개를 더 설치하겠습니다 를 의미하는데, (3 / 3)개를 설치하는 순간 모든 영역이 커버되어 진다. 즉 ! 나머지 부분이 없다는 것을 의미한다. 따라서 뒤에 '+1'이 붙으면 안되는 경우이다. 남은 부분이 없는데 왜 남은 부분을 위해서 하나를 더 설치해야 할까? 이런 상황인 것이다.

정리해보자.

전파범위가 w인 기지국이 있다. 이 기지국이 커버할 수 있는 아파트의 갯수는 #1에서 이야기했듯이 w * 2 + 1 개가 된다.

편의상, w * 2 + 1 = A 라고 표현해보자. 이 때 ! 커버해야 할 아파트의 갯수가 K개 있다면 설치해야 할 최소 기지국의 갯수는

다음과 같다.

1. if) (K % A != 0) : (K / A) + 1

2. if) (K % A == 0) : (K / A)

위와 같이 정리할 수 있다.

 

#3. 문제풀이

#1과 #2에서 전파범위와 커버영역 뭐 이런 이야기들을 했다. 그런데 #2에서 "매우중요" 라고 표시해놓은 한 문구가 있다.

바로 우리가 위의 수식들을 구할 때 했던 하나의 가정인데 "커버 받아야 할 아파트들을 연속적으로 존재한다." 라는 가정이였다.

우리는 이제 이 문구를 가정이 아닌 실제로 문제에 대입해서 풀 것이다. 지금부터 알아보자.

우리는 아파트의 영역을 크게 3가지 영역으로 나눌 것이다.

A. 1번 아파트부터 첫 번째 기지국까지의 커버하는 영역

B. 기지국과 기지국 사이 사이의 영역

C. 마지막 기지국부터 마지막 아파트까지의 영역

쉽게 문제에 주어진 첫 번째 예시를 가져와보자. [ N = 11 / [ 4 , 11 ] , 1 ] 그림으로 표현하면 다음과 같다.

위와 같은 경우이다. 가장 먼저 ! 우리는 전파범위(w) 가 1이라는 것을 알고 있으니, 한 개의 기지국이 커버할 수 있는 아파트의 갯수부터 구해놓고 시작을 하자. 한 개의 기지국이 커버할 수 있는 아파트의 갯수는 w * 2 + 1 = 3 이 된다.

즉 ! 한 개의 기지국이 3개의 아파트까지 커버를 할 수 있는 상황이다.

먼저, 영역 A를 살펴보자. 영역 A를 색깔로 표시하면 다음과 같다.

영역 A는 1번 아파트부터 첫 번쨰 기지국 사이에 있는 아파트들 중, 전파를 받지 못하는 아파트들의 영역이다.

즉 ! 위와 같이 2칸이 존재한다. 우리는 #1과 #2에서 모든 세팅을 다해놨기 때문에 계산을 너무나도 쉽게 할 수 있다.

전파를 받아야 할 아파트가 2개이고, 한 개의 기지국이 커버할 수 있는 아파트가 3개일 때, 필요한 기지국의 최소갯수는 ?

바로, (2 / 3) + 1 = 1개 이다. 즉 ! 파랑색 부분에서 기지국을 최소 1개를 더 설치해 주어야 한다는 것이다.

 

영역 B를 살펴보자. 영역 B를 색깔로 표시하면 다음과 같다.

영역 B는 기지국과 기지국 사이에 있는 아파트들 중, 전파를 받지 못하는 아파트들의 영역이다.

즉 ! 위와 같이 4칸이 존재한다.

전파를 받아야 할 아파트가 4개이고, 한 개의 기지국이 커버할 수 있는 아파트가 3개일 때, 설치해야 할 기지국의 최소갯수는 ?

바로, (4 / 3) + 1 = 2개 이다. 즉 ! 영역 B에 기지국을 최소 2개를 더 설치해 주어야 한다는 것이다.

 

마지막으로 영역 C를 살펴보자. 사실 위의 예시에서는 영역 C가 존재하지 않는다.

왜냐하면 영역 C는 마지막 기지국과 마지막 아파트 사이에 있는 아파트들 중, 전파를 받지 못하는 영역인데, 위의 예시에서는 가장 마지막 아파트에 기지국이 설치되어 있어서 위의 예시에서는 존재하지 않는다.

대신 ! 위의 예시에서 N = 15로 바꿔본다면 다음의 영역이 C에 해당하게 된다.

위의 예시에서 N = 15로 바꿨을 때, 영역 C에 해당하는 부분이다. 이 부분은 원래의 문제에는 없던 것이므로 따로 계산은 하지 않겠다. 이렇게 우리는 1번 아파트와 첫번쨰 기지국, 기지국과 기지국, 마지막 기지국과 마지막 아파트 사이사이에 존재하는 아파트들 중에서 전파를 받지 못하는 아파트들의 갯수만 알 수 있다면 #1과 #2의 내용을 통해서 쉽게 계산을 할 수 있다.

 

#4. 코드 설명

int Install(int Start, int End, int W)
{
	int Install_Range = End - Start + 1;
	int Cover_Range = W * 2 + 1;

	if (Install_Range <= 0) return 0;
	if (Install_Range % Cover_Range == 0) return Install_Range / Cover_Range;
	return (Install_Range / Cover_Range) + 1;
}

본인이 구현한 "설치해야 할 기지국의 최소 갯수"를 구하는 함수이다.

함수의 매개변수부터 의미를 알아보자.

Start = 현재 영역에서 전파를 받지 못하는 첫 번째 아파트의 위치

End = 현재 영역에서 전파를 받지 못하는 마지막 아파트의 위치

W = 전파범위

그리고 위의 예시에서 영역 A를 기준으로 이야기를 해보자.

Start = 1

End = 2

End가 2인 이유는 "4번에 기지국이 설치되어 있고 이 기지국으로 인해서 3번 아파트까지는 전파를 받게 된다. 즉 ! 1번과 4번 사이에 있는 아파트들 중, 전파를 받지 못하는 마지막 아파트는 2번" 이 된다.

설치해야 할 아파트의 갯수는 2개가 된다. 그리고 "매우중요" 하다고 표시해놓은 가정과 같이, 이 2개의 아파트는 연속적으로 존재하고 있다.

즉 ! Install_Range라는 변수에는 "전파를 받아야 할 아파트의 갯수" 가 저장된다.

그리고 Cover_Range는 "한 개의 기지국이 커버할 수 있는 아파트의 갯수" 가 저장된다.

우리는 이 2개의 값만 알면 설치해야 할 기지국의 최소갯수는 쉽게 구할 수 있다.

나누어 떨어지는지 아닌지에 따라서 구분만 해주면 구할 수 있다. 이를 구해주는 과정이 가장 마지막에 있는 2개의 return 문이다.

그럼 ! 중간에 있는 Install_Range <= 0 의 조건문에 대해서 생각을 해보자.

위의 예시에서 1번 아파트에 기지국이 추가적으로 설치되어 있었다고 생각을 해보자.

이런 경우이다. 이 때 영역 A를 구하기 위해서 함수를 호출하게 되면 다음과 같이 호출될 것이다.

Start = 1

End = -1

여기서 End가 -1이 되는 이유는, 첫 번째 기지국 기준으로 왼쪽으로 커버를 한다고 가정을하면 아마 0번 아파트까지 커버를 할 수 있을 것이고 -1번 아파트부터 커버가 되지 않을 것이다.

즉 ! 영역A는 "1번 아파트부터 첫 번째 기지국이 커버하지 못하는 1번과 가장 가까운 영역, 즉, -1번 아파트 사이에 몇 개의 기지국을 설치해야 할까?" 라는 말도 안되고 이해도 되지 않는 상황이 발생하게 된다.

따라서 이런 경우를 넘기기 위한 조건문이다.

 

[ 소스코드 ]

#include <vector>
using namespace std;
 
int Install(int Start, int End, int W)
{
    int Install_Range = End - Start + 1;
    int Cover_Range = W * 2 + 1;
 
    if (Install_Range <= 0) return 0;
    if (Install_Range % Cover_Range == 0) return Install_Range / Cover_Range;
    return (Install_Range / Cover_Range) + 1;
}
 
int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
 
    for (int i = 0; i < stations.size(); i++)
    {
        if (i == 0) answer = answer + Install(1, stations[i] - w - 1, w);
        else answer = answer + Install(stations[i - 1] + w + 1, stations[i] - w - 1, w);
    }
    answer = answer + Install(stations[stations.size() - 1] + w + 1, n, w);
 
    return answer;
}