[BOJ] 귀여운 라이언 15565번 C++

 

문제

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)

둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)

출력

K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.

 

접근 방식

 

중요한 것은 라이언 인형의 누적 개수이다

즉, 라이언 인형의 누적 합 배열에 누적 개수를 더해주면 되는데

이때, 만약 어피치 인형이 놓여져있다면 이전 누적 개수를, 라이언 인형이 놓여져 있다면 이전 누적 개수에 + 1 을 더해주면 된다.

 

누적합을 모두 구했다면, K 개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 구하면 된다.

이 때, 투 포인터를 이용해 구할 수 있다

먼저 가장 left 값은 1, 가장 right 값을 K로 둘 수 있다

right가 N 이하일 때까지 반복문을 돌면서 현재 누적 값 중 라이언 인형이 K 개 이상이면 집합의 크기를 더 작은 값으로 변경해주면 된다.

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int N,K,mn = 1000001;

int pL[1000003];

int main() {
    cin>>N>>K;
    fill(pL, pL + N + 1, 0);

    for(int i=1; i<=N; i++) {
        int x; cin>>x;
        if(x == 1) pL[i] = pL[i-1] + 1;
        else pL[i] = pL[i-1];

    }

    int s = 1;
    int e = K;

    while(e <= N) {
        int tmp = pL[e+1] - pL[s];

        if(tmp >= K) {
            mn = min(mn, e-s + 1);
            s++;

        }
        else e++;
    }
    if(mn == 1000001) cout<<-1;
    else cout<<mn;
}