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

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

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

문제분석

1. 분류
   • 투포인터
   • 슬라이딩 윈도우
2. 문제설명
   • 횡단보도의 개수 N개 입력
   • 고장난 신호등의 개수 B개 그리고 좌표 입력
   • 탐색하고자 하는 길이 K 입력
   • 배열의 길이가 가변적일 때: 투 포인터, 배열의 길이가 고정적일 때: 슬라이딩 윈도우
   • 슬라이딩 윈도우 -> O(N)의 속도로 탐색

입력

10 6 5
2
10
1
5
9

출력

1

코드

#include<iostream>
#include<vector>

using namespace std;

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

    //횡단보도는 N개
    vector<int>cross(N);

    //고장난 신호등의 개수 B
    for (int x = 0; x < B; x++)
    {
        int tmp;
        cin >> tmp;
        cross[tmp-1]++;
    }

    //탐색해야하는 길이 K
    int broken = 0;
    for (int x = 0; x < K; x++)
    {
        broken += cross[x];
    }

    //슬라이딩 윈도우로 고장난 창문의 최소값을 구한다.
    int Min = broken;
    for (int x = 0; x <= N - K; x++)
    {
        broken -= cross[x];
        broken += cross[x+K];
        if(Min > broken) Min = broken;
    }

    cout << Min;

    return 0;
}

 

문제풀이

1. 탐색해야 하는 도로의 길이는 일정하다. 탐색 배열의 길이가 고정되어 있다. -> 슬라이딩 윈도우 알고리즘을 활용한다.
2. 횡단보도는 N개 있다. -> 전체 배열의 길이는 N이다. vector<int>cross(N);
3. 고장난 신호등의 개수는 B개 이다. -> B번 반복문을 실행하여, 고장난 신호등의 정보를 입력한다. 
4. 신호등이 연속적으로 K개 작동해야 한다. -> 0 ~ K 까지의 배열의 고장난 신호등 개수를 탐색한다.
5. 각 구간의 고장난 신호등의 개수 중에서 최소값이 정답이다.