[백준] 14465번 소가 길을 건너간 이유 5

✔️ 문제 링크

https://www.acmicpc.net/problem/14465

14465번: 소가 길을 건너간 이유 5

---

✔️ 문제 이해

◾ 일자형 길에 횡단보도 N개가 있다. (1 ≤ N ≤ 100,000)

◾ 뇌우로 인해 몇몇 횡단보도가 고장나있다.

◾ 연속한 K개의 신호등이 존재하도록 신호등을 수리하려고 한다.

◾ 연속한 K개의 신호등이 존재하도록 최소 몇 개의 신호등을 수리해야 하는지 출력한다. 

---

✔️ 설계

◾ 수리한 신호등의 개수를 이분 탐색을 통해 찾는다.

◾ 이분 탐색의 과정에서 구해지는 수리한 신호등의 개수에 대해, K 개의 신호등이 연속할 수 있는지 슬라이딩 윈도우를 통해 판별한다. 

---

✔️ 문제 회고

◾ 이분 탐색과 슬라이딩 윈도우를 사용한 풀이보다 훨씬 간결하고 빠르게 짤 수 있는 문제였다.

◾ 슬라이딩 윈도우만 사용하는 방법인데, 매우 간단하다. K만큼 윈도우를 이동시키면서, K길이에 고장난 신호등이 몇 개 있는지 체크하면된다. 모든 K 길이의 구간에 대해 가장 적게 고장난 신호등 개수를 구하면 된다. 

◾ 처음엔 슬라이딩 윈도우를 덱으로 구현했는데, 간단히 배열로 구할 수 있었다. (앞뒤만 고려하는 방법)

◾ 슬라이딩 윈도우를 사용하여 간단히 풀 수 있는 문제였다. 문제 분류가 이분 탐색으로 되어있어서 이분 탐색을 써야만 한다는 생각 때문에 처음에 비효율적으로 구현한 것 같다. 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

int main() {
	int n, k, b;
	bool arr[100001] = { false };

	cin >> n >> k >> b;

	for (int i = 0; i < b; i++) { // 고장난 신호등 정보를 bool 배열에 기록
		int num;
		cin >> num;
		arr[num] = true;
	}

	int low = 0, high = 100000; // 0개를 수리해도, 조건을 만족할 수 있다.
	int ret = 100000;

	while (low <= high) {
		int mid = (low + high) / 2; // 수리한 신호등의 개수 
		bool flag = false;
		deque<int> window;

		// 덱을 사용한 슬라이딩 윈도우로 연속한 k개의 신호등이 연속돼있는지 확인한다. 
		for (int i = 1; i <= n; i++) {
			if (i > k && !window.empty() && window.front() <= i-k)
				window.pop_front();

			if (!arr[i])
				window.push_back(i);
   
			if (i >= k && k - window.size() <= mid) {
				flag = true;
			}
		}

		if (flag) { // mid개이하 만큼 신호등을 수리 했을때 K개의 신호등이 연속돼있다면,
			ret = min(ret, mid); // 최소 수리 개수를 구한다.
			high = mid - 1; // 신호등을 더 적게 수리해본다. 
		}
		else { // mid개이하 만큼 신호등을 수리 했을때 K개의 신호등이 연속 되지 않다면,
			low = mid + 1; // 신호등을 더 많이 수리해본다.
		}
	}

	cout << ret;

	return 0;
}

 

👨🏻‍💻 개선된 소스 코드

#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

int main() {
	int n, k, b;
	bool arr[100001] = { false };

	cin >> n >> k >> b;

	for (int i = 0; i < b; i++) {
		int num;
		cin >> num;
		arr[num] = true;
	}

	int broken = 0;

	for (int i = 1; i <=k; i++) {
		if (arr[i])
			broken++;
	}

	int ret = broken;

	for (int i = k + 1; i <= n; i++) { 
		if (arr[i])
			broken++;
		if (arr[i - k])
			broken--;

		ret = min(ret, broken);
	}

	cout << ret;
	return 0;
}