[BOJ] 14465번 "소가 길을 건너간 이유 5" C언어 풀이

문제

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

입력

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

출력

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

 

---

입력 예시

10 6 5
2
10
1
5
9

출력 예시

1

답안

코드

#include <stdio.h>
#pragma warning(disable: 4996)
#define _CRT_SECURE_NO_WARNINGS

int main() {

	int arr[100001] = { 0 };
	int N, K, B, num, count = 0, min = 1000000;
	
	scanf("%d %d %d", &N, &K, &B);
	
	for (int i = 0; i < B; i++) {
		scanf("%d", &num);
		arr[num] = 1;
	}
	for (int i = 1; i+K-1 <= N; i++) {
		count = 0;
		for (int j = i; j < i + K; j++) {
			if (arr[j] == 1)
				count++;
		}
		if (count < min)
			min = count;	
	}
	printf("%d", min);

	return 0;
}

 

풀이

 첫 줄에 횡단보도의 갯수(신호등의 갯수), 연속해야하는 신호등의 갯수, 고장난 신호등의 번호가 주어진다.  두 번째 줄 부터는 고장난 신호등의 번호가 주어진다. 

 

따라서 우리는 반복문을 돌면서 각 인덱스 마다 연속해야하는 신호등의 갯수를 충족하기 위해서는 얼마나 필요한지 계산을 하게 된다. 그렇게 반복문을 돌면서 연속해야하는 신호등의 갯수를 충족하기 위해 수리해야하는 횟수를 count에 저장한다. 그리고 count의 값이 min 값보다 작으면 min 값을 count 값으로 업데이트 한다. 이를 배열 끝까지 반복한 후 min 값을 출력한다.