백준 14465 소가 길을 건너간 이유 5 (USACO February 2017 Silver 2번)

문제 링크: https://www.acmicpc.net/problem/14465

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

1. Sliding Window, Line Sweeping

처음 k개중에 작동하는 신호등의 갯수를 센 후에, 계속 k개 구간을 유지하면서 작동하는 신호등의 갯수를 update시켜주면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int n, k, b, broken[100001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k >> b;
    while(b--) {
        int x;
        cin >> x;
        broken[x] = 1;
    }
 
    int ans = 0;
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(i <= k) {
            if(broken[i] == 0) cnt++;
            continue;
        }
        if(broken[i] == 0) cnt++;
        if(broken[i - k] == 0) cnt--;
        ans = max(ans, cnt);
    }
 
    cout << k - ans << '\n';
    return 0;
}
 

2. Prefix Sum

#include <bits/stdc++.h>
using namespace std;
 
int n, k, b, broken[100001], pSum[100001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k >> b;
    while(b--) {
        int x;
        cin >> x;
        broken[x] = 1;
    }
 
    for(int i = 1; i <= n; i++)
        pSum[i] = pSum[i - 1] + (1 - broken[i]);
 
    int ans = 1e9;
    for(int i = k; i <= n; i++)
        ans = min(ans, k - (pSum[i] - pSum[i - k]));
 
    cout << ans << '\n';
    return 0;
}