[백준 14465] 소가 길을 건너간 이유 (C++)

문제

---

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

 

입력

---

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

 

출력

---

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

 

문제 풀이

---

슬라이딩 윈도우 문제.

 

1번부터 N번까지 신호등이 고장났는지 여부를 저장하는 boolean 타입 배열을 생성한다. 처음에는 1번부터 K번까지 고장난 신호등의 개수(= 수리해야 하는 신호등의 개수)를 정답을 나타내는 변수인 answer에 저장한다. 그 이후 N까지 윈도우를 한 칸씩 밀면서 그 상태의 윈도우에서 수리해야 하는 신호등의 개수를 구한다. 한 칸 밀어내므로 현재 윈도우의 맨 뒤 신호등이 i번이라고 하면 i-K번은 윈도우에서 벗어난다. 만약 i-K번 신호등이 고장났으면 이전 수리해야 하는 신호등의 개수에서 1이 빠지게 된다. 그리고 맨 뒤 신호등이 고장났다면 이전 수리해야 하는 신호등의 개수에서 1이 추가가 된다. 각 상태마다 최솟값과 비교하고 저장하며 최종 최솟값을 구해주면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;
bool* isBroken;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M, B, num;
	cin >> N >> M >> B;
	int answer = 0;
	isBroken = new bool[N+1];
	for (int i = 0; i < N+1; i++)
	{
		isBroken[i] = false;
	}
	for (int i = 0; i < B; i++)
	{
		cin >> num;
		isBroken[num] = true;
	}
	for (int i = 1; i <= M; i++)
	{
		if (isBroken[i] == true)
		{
			answer++;
		}
	}
	int tempAnswer = answer;
	for (int i = M + 1; i <= N; i++)
	{
		if (isBroken[i - M] == true)
		{
			tempAnswer--;
		}
		if (isBroken[i] == true)
		{
			tempAnswer++;
		}
		answer = min(answer, tempAnswer);
	}
	cout << answer << "\n";
	return 0;
}