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

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

 

N개의 신호등 중 B개가 고장 나 있을 때,  연속으로 K개가 존재하도록 고쳐야 하는 최소 신호등의 개수를 출력하는 문제이다.

 

N = 10, B = 5, K = 6 일 때, 최소로 고쳐야 하는 신호등의 개수를 구하기 위해 1개를 고치는 경우부터 B개를 고치는 경우까지 모두 확인할 수도 있다. 그러나 이 방법은 높은 시간 복잡도를 가진다. 슬라이딩 윈도우 기법을 이용하여 연산 과정을 줄여보자.

 

고장난 신호등은 보라색

 

슬라이딩 윈도우 기법은 연속된 영역에서 특정 값을 계산하여 비교할 때 사용한다. 슬라이딩 + 윈도우 = 미끄러지는 창문이라는 뜻으로, 일정 크기의 창문처럼 보이는 영역이 1 단위씩 오른쪽으로 이동하여 특정 값을 계산한다. 연속된 신호등이 K 개라는 뜻은, 크기가 K인 창문 내의 신호등이 모두 완전하다는 이야기이다. 따라서 크기가 K개인 창문을 오른쪽으로 이동시키면서 창문 내의 모든 신호등이 완전하기 위해 고쳐야 하는 신호등 개수를 구한다.

 

창문의 시작 위치가 1일 때

 

먼저 창문의 시작 위치가 1일 때, 1 ~ K(6) 까지 고쳐야 하는 신호등의 개수를 구해보면 cnt = 3개이다. 이제 이 창문의 시작 위치를 1씩 이동해본다.

 

창문의 시작 위치가 2일 때

 

2부터 시작하는 창문 내에서 고쳐야 하는 신호등의 개수를 구하기 위해 창문 내의 모든 신호등을 다시 체크할 필요가 없다. 아까의 창문과 비교했을 때, 1은 나가고 7이 들어왔으므로 기존의 고쳐야 하는 신호등 개수 3개를 적절히 조정해주기만 하면 된다. 고장 난 신호등이었던 1이 빠졌으므로, cnt=3은 2가 된다. 새로 들어온 7은 고장 난 신호등이 아니므로, 여전히 cnt는 2로 유지된다. 

 

즉, 이전에 구해놓았던 고칠 신호등 개수(cnt)를 기준으로,  이번 창문에서 빠진 신호등이 고장난 것이었다면 cnt = cnt - 1 이 된다. 이번 창문에 새로 들어온 신호등이 고장난 것이라면, cnt = cnt + 1이다. 

 

창문의 시작 위치가 3일 때

 

창문을 하나 더 이동시켜보자. 이전의 cnt 값은 2 였다. 이번 창문에서 빠진 신호등 2번은 고장 난 신호등이었으므로, 고장 난 신호등의 개수 2에서 1을 빼주어야 한다. 이번 창문에 새로 들어온 신호등 8번은 고장 난 신호등이 아니므로 cnt를 유지시킨다. 따라서 cnt 개수는 1 이 된다.

 

이와 같이, 슬라이딩 윈도우 기법을 사용하면 이번 창문과 이전 창문의 공통적인 부분을 제외하고 새로운 부분만 다시 확인함으로써 연산 과정을 줄일 수 있다.

 

창문의 시작 위치가 5일 때

 

창문의 시작 위치는 1번 부터 5(N-K+1) 번까지 순회한다. 우리는 창문 내 고쳐야 하는 신호등 개수 중 최소 개수를 구해야 하므로 최솟값을 계속해서 기록한다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int N, K, B;
bool point[100001];

int main() {

    scanf("%d %d %d", &N, &K, &B);
    memset(point, true, sizeof(point));

    for (int i=0; i<B; i++) {
        int b;
        scanf("%d", &b);
        point[b] = false;
    }

    int cntB = 0;
    for (int i=1; i<=K; i++)
        if (!point[i]) cntB++;
    
    int minB = cntB;
    for (int i=2; i<= N-K+1; i++) {
        if (!point[i-1]) cntB--;
        if (!point[i+K-1]) cntB++;
        minB = min(minB, cntB);
    }
    printf("%d", minB);
    return 0;
}