Programmers [기지국 설치]

#include <iostream>
#include <vector>
using namespace std;
int solution(int n, vector<int> stations, int w)
{
	int head = 0, tail = 0, answer = 0;
	int cur, val;
		for (int i = 0; i < stations.size(); i++) {
			cur = stations[i];
			tail = cur - w - 1;
			if (tail>=head && tail!=0) {
				val = tail - head + 1;
				if ((val % (2 * w + 1)) == 0)
					val = (val / (2 * w + 1));
				else
					val = (val / (2 * w + 1)) + 1;
				answer += val;
			}
			head = cur + w + 1;
			if (head > n) break;
		}
		if (head <= n) {
			tail = n;
			val = tail - head + 1;
			if ((val % (2 * w + 1)) == 0)
				val = (val / (2 * w + 1));
			else
				val = (val / (2 * w + 1)) + 1;
			answer += val;
		}
	return answer;
}
int main() {

	int n =7;
	vector<int> stations = {2,5};
	int w =1;

	solution(n, stations, w);

	return 0;
}

 

사실 이 문제는 생각 없이 배열 탐색을 통한 구현을 했는데(문제의 input범위가 n의 범위가 2억, stations의 범위가 10000이었다....) 

 

귀신같이 시간초과가나서 다시 구현했다.

 

그래도 배열탐색으로 구현한 코드를 저장해둘걸... 아쉬움이 남는다.