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

> 문제

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

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

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

> 풀이

K개의 연속한 신호등이 존재하기 위해 고쳐야하는 신호등 개수를 찾는 문제이므로, i를 0부터 시작해서 숫자를 키워가며 고장난 신호등 중 i개를 선택하여 고친 후, K크기의 슬라이딩 윈도우를 이용하여 해당 윈도우 안에 고장난 신호등이 없는지 확인하고 모두 탐색할 생각이었다. i를 조금 더 효율적으로 찾기 위해 binary search를 사용하면 좋겠다고 생각했지만, 문제는 고장난 신호등 중엥 i개의  신호등을 어떻게 고를 것인가였다. 완탐으로 모두 선택하는 경우가 있었지만 너무 비효율적인 코드라고 생각했다. 하지만 생각해보니, 슬라이딩 윈도우를 사용하는 경우 굳이 신호등을 선택하여 고친 후 윈도우안에 고장난 신호등의 존재 유무를 볼 필요없이 윈도우 안에 고장난 신호등의 개수를 확인하고 가장 작은 값을 리턴하면 쉽게 알 수 있었다.

#include <string>
#include <vector>
#include <limits.h> 
using namespace std;

int main()
{
    int N, K, B;
    scanf("%d %d %d", &N, &K, &B);
    vector<int> TraifficLights(N, 0);
    
    int temp = 0;
    for (int b = 0; b < B; b++) {
        scanf("%d", &temp);
        TraifficLights[temp-1] = 1;
    }

    int ans = INT_MAX;
    
    for (int i = 0; i < N-K+1; i++) {
        temp = 0;
        for (int j = i; j < i+K; j++) {
            temp += TraifficLights[j];
        }
        ans = ans < temp ? ans : temp;
    }
    printf("%d", ans);
    return 0;
}

> 결과