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

문제

소가 길을 건너간 이유 5

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

 

 

풀이

설명

최소 몇 개의 신호등을 수리해야 하는지를 구하는 문제입니다.

 

누적합과 슬라이딩 윈도우를 이용해 해결할 수 있습니다.

 

예시 코드

function solution() {
  const [N, K, B] = input().split(" ").map(Number);
  const broken = Array(N + 1).fill(0);
  for (let i = 1; i <= B; i++) {
    broken[+input()] = 1;
  }

  const sum = Array(N + 1).fill(0);
  for (let i = 1; i <= N; i++) {
    sum[i] = sum[i - 1] + broken[i];
  }

  let minBroken = Infinity;
  for (let i = K; i <= N; i++) {
    let brokenInRange = sum[i] - sum[i - K];
    minBroken = Math.min(minBroken, brokenInRange);
  }

  return minBroken;
}