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

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

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

<문제>

선형에서의 슬라이딩 윈도우, 입력으로 들어온 인덱스를 chk[input]=true, 윈도우의 초기설정을 해주고

right<=n일때까지 구간내 chk가 true인 개수를 score, ans를 score와 최소로 갱신하며 진행한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, k, b, ans = 1e9;
bool chk[100001];
int main(void) {
    cin >> n >> k >> b;
    while (b--) {
        int x;
        cin >> x;
        chk[x] = true;
    }
    int i, cnt = 0, l = 1, r = k;
    for (i = 1; i <= k; i++) cnt += chk[i];
    while (r <= n) {
        ans = min(cnt, ans);
        cnt -= chk[l++];
        cnt += chk[++r];
    }
    cout << ans;
    return 0;
}