[백준/C++] 소가 길을 건너간 이유 5

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

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

해당 문제를 투포인터의 아이디어를 차용해서 풀어봤습니다.(사실 이중 for문으로 풀었다고 해도 맞는 말인것 같습니다) 문제 설명부터 하겠습니다.

• 신호등의 개수가 N으로 주어지고
• 부서진 신호등의 개수가 B로 주어집니다.
• 부서진 신호등은 수리가 가능하고, 최소한의 수리 횟수로 연속한 K개의 신호등을 만들어야 합니다.

해당 문제를 푼 아이디어를 나열하면 다음과 같습니다.

• 총 두개의 포인터를 사용합니다 (편의상 각각 Anchor와 Move로 명명했습니다)
• Anchor 포인터는 모든 배열의 원소를 시작지점으로 삼는 포인터입니다.
• Move 포인터는 Anchor포인터로부터 K 칸을 진행하면서 부서진 신호등의 개수를 카운트 합니다.
• 각 Anchor 포인터 시작점 마다 카운트한 부서진 신호등 수의 minimum 값이 최종 출력물입니다.

시간복잡도를 생각해보면 두 포인터가 배열을 탐색하면서 특정 원소들을 비교를 하는데, Anchor 포인터는 N-K번 이동하고, Anchor 포인터의 이동마다 Move 포인터가 K번 이동함으로 O(N)입니다.

 

더보기란에 코드 첨부하겠습니다.

#include <iostream>

using namespace std;

int N, K, B;
bool isBroken[100001];

int main() {
	cin >> N >> K >> B;
	for (int i = 1; i <= B; i++) {
		int input; cin >> input;
		isBroken[input] = true;
	}
	int result = 100001;
	for (int anchor = 1; anchor <= N - K + 1; anchor++) {
		int cnt = 0;
		for (int move = anchor; move < anchor + K; move++) {
			if (isBroken[move]) cnt++;
		}
		result = min(result, cnt);
	}
	cout << result;
}