[프로그래머스] Level 3 : 기지국 설치

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

프로그래머스

 

딱히 알고리즘이 없는 수학 구현 문제이다.

설명은 코드의 주석으로 한다.

#include <vector>
using namespace std;

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

	// 각 기지국의 전파 범위를 pair로 저장 (최솟값 1, 최댓값 n)
	for (const auto& station : stations)
		Save.push_back({ max(station - w, 1), min(station + w, n) });

	int Cur = 1; // 현재 검사 위치
	for (const auto& i : Save)
	{
		// 가장 처음 구간에 전파가 도달한 경우
		if (i.first == 1)
		{
			// 해당 전파의 전달 범위 + 1로 검사 위치를 옮긴다.
			Cur = i.second + 1;
			continue;
		}

		// 기지국의 전파가 겹치게 연결되어있는 경우
		if (i.first <= Cur)
		{
			// 해당 전파의 전달 범위 + 1로 검사 위치를 옮긴다.
			Cur = i.second + 1;
			continue;
		}

		int a = i.first - Cur;
		int b = (w * 2) + 1; // 전파 범위
		answer += (a - 1) / b + 1; // 나눗셈 올림 공식
		Cur = i.second + 1;
	}

	// 모든 기지국의 전파 범위를 검사했는데, 모든 아파트를 검사하지 않은 경우
	if (Save[Save.size() - 1].second != n)
	{
		// 최대 아파트 수 에서 최대 전파 전달 위치를 뺸 아파트 수에 대해 검사
		int a = n - Save[Save.size() - 1].second;
		int b = (w * 2) + 1;
		answer += (a - 1) / b + 1;
	}

	return answer;
}