[프로그래머스] 기지국 설치 - LEVEL 3

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 특정 알고리즘 없이 구현하여 풀이했다. 첫 아파트부터 시작해 다음 기지국의 범위가 시작되기 직전까지 기지국의 전파가 닿지 않는 범위의 크기를 구하고, 이 크기를 한 기지국의 범위 크기로 나누어 해당 구간에는 몇 개의 기지국을 설치해야하는지 파악하는 방식을 사용했다.

1) 범위의 시작인 curIndex를 첫 아파트의 번호인 1로 초기화한다.

2) 기지국이 설치된 개수인 stations의 크기만큼 for문을 돌며 아래 과정을 반복한다.

• curRange 변수를 선언해 curIndex ~ 현재 순서 기지국인 stations[i]의 범위의 맨 앞 사이의 거리로 초기화한다. (== 기지국 전파 닿지 않는 범위)
• 해당 범위를 한 기지국을 설치했을 때 전파가 닿는 범위의 크기인 2 * w + 1로 나누고, 이를 반올림하여 현재 범위에서 필요한 기지국의 수를 구한다.
• 구한 값을 answer에 누적시킨다.
• curIndex를 현재 순서 기지국인 stations[i]의 범위의 맨 뒤로 초기화 하여 다음 범위부터 다시 확인한다.

3) 위 과정을 반복한 이후 curIndex가 아파트 개수인 n보다 작거나 같다면 마지막 기지국의 뒤 쪽으로 전파가 닿지 않는 범위가 남아있는 것이기 때문에 해당 범위에 대해서도 필요한 기지국 수를 구해 answer에 누적해준다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n, vector<int> stations, int w)
{
	int answer = 0, curIndex = 1;

	for (int i = 0; i < stations.size(); i++)
	{
		int curRange = stations[i] - w - curIndex;
		answer += ceil(curRange / (2.0 * w + 1));
		curIndex = stations[i] + w + 1;
	}

	if(curIndex <= n)
		answer += ceil((n + 1 - curIndex) / (2.0 * w + 1));

	return answer;
}