[문제풀이] 백준 14465 - 소가 길을 건너간 이유 5

📢 문제

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

📢 알고리즘

슬라이딩 윈도우, 누적합

📢 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<bool> v; //신호등

int main()
{
  int N, K, B;
  cin >> N >> K >> B; //연속 K개의 신호등
  v.resize(N + 1, false);
  for (int i = 0; i < B; i++)
  {
    int j; //고장난 신호등 번호
    cin >> j;
    v[j] = true;
  }

  int minCnt = 0; //고장난 신호등 최소 개수
  int cnt = 0;

  // 1번~K번까지의 고장난 신호등 개수
  for (int i = 1; i <= K; i++)
  {
    if (v[i])
    {
      cnt++;
      minCnt++;
    }
  }

  int start = 1;
  int end = K;
  while (start < end && end <= N)
  {
    if (v[start])
    {
      cnt--;
    }
    start++;
    end++;
    if (v[end])
    {
      cnt++;
    }
    minCnt = min(minCnt, cnt);
  }
  cout << minCnt;
}

참고
https://yongmemo.tistory.com/16 (사진출처)