문제
꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 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;
}
'Algorithm' 카테고리의 다른 글
[BOJ] 사과나무 19539번 C++ (0) | 2024.09.11 |
---|---|
[BOJ] 귀찮음 16208번 C++ (0) | 2024.09.11 |
[BOJ] 가운데를 말해요 1655번 C++ (2) | 2024.09.04 |
[BOJ] 쇠막대기 10799번 C++ (0) | 2024.09.04 |
[BOJ] 괄호의 값 2504번 C++ (0) | 2024.09.03 |