[Programmers] 기지국 설치

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

알고리즘은 아래와 같습니다.

1. 전파가 터지지 않는 범위들을 구합니다.

2. 전파가 터지지 않는 범위 내 설치할 기지국 갯수는 (전파 터지지 않는 범위 / 기지국 범위)의 올림입니다.

2.1 기지국이 소수점 개수로 있을 수 없기 때문입니다.

3. 2번 공식을 통해 1번에서 구한 범위들 내 기지국 개수를 모두 파악한 뒤 반환해줍니다.

 

	#include <iostream>
	#include <vector>
	using namespace std;
	int solution(int n, vector<int> stations, int w)
	{
	vector<pair<int, int>> notReachedRanges;
	int start = 1;
	for (int station : stations)
	{
	if (start < station - w)
	{
	notReachedRanges.push_back({ start, station - w - 1 });
	}
	start = station + w + 1;
	}
	if (start <= n)
	{
	notReachedRanges.push_back({ start, n });
	}
	int answer = 0;
	int radioWave = 2 * w + 1;
	for (pair<int, int> range : notReachedRanges)
	{
	int len = range.second - range.first + 1;
	if (len <= radioWave)
	{
	answer++;
	}
	else
	{
	answer += len / radioWave + (len % radioWave != 0);
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~