[c++] 15565번: 귀여운 라이언

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

15565번: 귀여운 라이언

 

문제 요약

 

라이언 인형과 어피치 인형 N개 일렬로 놓여있다. 라이언 인형은 1, 어피치 인형은 2.

라이언 인행 K개 이상있는 가장 작은 연속된 인형들의 집합 크기 구하기

(집합없으면 -1 출력)

 

범위 

 

1 ≤ K ≤ N ≤ 10^6

 

---

 

L의 범위는 1부터 N, R의 범위는 0부터 N이다. (k=1일수있기 때문에 L의 시작 위치가 N이어도 괜찮다)

만약 R 위치의 원소가 1이라면 라이언 인형이므로 횟수(cnt)를 증가시킨다.

그리고 다음 L 케이스를 진행할 때, 앞에 했던 cnt를 다시 사용하기 위해 L-1 위치의 원소가 1이라면 cnt를 감소시키고 아니면 그대로 진행한다. R이 배열의 길이를 초과했거나 cnt가 k보다 크다면 while 반복문에서 나와서 최소값을 업데이트 한다. 

 

만약 최소값(minS)이 초기값과 동일하다면 k개 이상의 라이언 인형이 포함되는 집합이 없었다는 뜻이므로 -1을 출력한다.

 

minS 최소값 범위를 정해줘야 하는데, 나올 수 있는 가장 큰 값보다 +1 인 값으로 정해줬다. 여기서 나올 수 있는 가장 큰 값은

N이 10^6인 상태에서 처음부터 끝까지 = 집합의 범위 인 경우를 뜻하기 때문에 minS의 값을 10^6+1 으로 해줬다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int n, k, doll[1000002], minS = 1000001;

void input(){
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> doll[i];
}

void solution(){
    int cnt = 0, R = 0;
    for(int L=1; L<=n; L++){
        if(doll[L-1] == 1) cnt--;
        while(R+1<=n && cnt < k){
            if(doll[++R] == 1) cnt++;
        }
        if(cnt >= k) minS = min(R-L+1, minS);
    }
    if(minS == 1000001) cout << "-1\n";
    else         cout << minS << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!