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

작성일 | In

문제 링크

  • http://icpc.me/14465

문제 출처

  • USACO 2017 February Contest Silver 2번

풀이

먼저 각 신호등이 고장났는지 저장을 해줍니다.
그 다음에 모든 i에 대해 [i, i+k)를 정상적으로 작동시키기 위한 개수를 각각 구해주는 방식으로 정답을 구해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int arr[101010];
int n, k, b;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> b;
	for(int i=0; i<b; i++){
		int x; cin >> x;
		arr[x] = 1;
	}

	for(int i=1; i<=n; i++) arr[i] += arr[i-1];

	int ans = 1e9+7;
	for(int i=1; ; i++){
		if(i+k-1 > n) break;
		ans = min(ans, arr[i+k-1] - arr[i-1]);
	}
	cout << ans;
}