문제 푼 날짜 : 2021-10-06

문제

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

접근 및 풀이

슬라이딩 윈도우 알고리즘을 이용하는 문제였다.

코드는 아래의 생각대로 구현하였다.

1. 문제에 주어진 최대 크기의 배열을 선언하고, 정상적인 신호등은 0, 고장난 신호등의 위치에는 1의 값을 준다.
2. 최초에 K개 만큼 신호등을 세어준다. 이 때, 고장난 것을 따로 세어준다.
3. K+1 부터 N까지 탐색하면서 인덱스가 가장 낮은 위치의 신호등을 빼주고 다음 위치의 신호등을 추가해준다. 이 때, 고장난 신호등인지 체크하여 K개의 신호등을 유지한 채로 고장난 신호등의 갯수 중 최솟값을 찾아준다.

코드

// 백준 14465번 : 소가 길을 건너간 이유 5
#include <iostream>

using namespace std;

int N, K, B, ans = 987654321;
int arr[100001];

int main() {
    cin >> N >> K >> B;

    for (int i = 0, num; i < B; i++) {
        cin >> num;
        arr[num] = 1;
    }

    int broken = 0;
    for (int i = 1; i <= K; i++) {
        if (arr[i] == 1) {
            broken++;
        }
    }
    ans = broken;
    for (int i = K + 1; i <= N; i++) {
        if (arr[i - K] == 1) {
            broken--;
        }
        if (arr[i] == 1) {
            broken++;
        }
        ans = min(ans, broken);
    }
    cout << ans;
    return 0;
}

결과

피드백

가끔 이런 유형의 문제가 나오는 사실을 알게 되었는데, 써먹기 유용한 알고리즘인 것 같다.