(C++) - 백준(BOJ) 15565번 : 귀여운 라이언

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

15565번: 귀여운 라이언

연속합 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 어피치 인형은 확인할 필요가 없습니다. 라이언 인형의 위치만 저장해 확인합니다. n, k를 입력해서 이를 vector 변수 lionIdx에 저장합니다.

 

📔 풀이과정

 저장된 라이언 인형들의 인덱스 정보들만 확인해줍니다. 예제를 통해 설명하자면 저장된 인덱스들의 정보는 이렇습니다. lionIdx = [0, 4, 6, 9]여기서 k를 포함하는 최소의 길이는 곧 연속하는 k개의 원소를 뽑아낸 뒤 그 값 차이의 최댓값 + 1이 됩니다. 연속하는 k = 3개의 원소를 뽑는 법은 [0, 4, 6] 또는 [4, 6, 9]입니다. 각각 6 - 0 + 1 = 7, 9 - 4 + 1 = 6이 길이가 됩니다. 7, 6 중 가장 짧은 길이는 6이므로 답이 6이 됩니다. 이 최솟값을 length에 저장합니다.

 

📔 정답출력

legnth를 출력합니다.

---

📕 Code

//귀여운 라이언
#include <bits/stdc++.h>
using namespace std;
int n, k, length = 0x3f3f3f3f;
vector <int> lionIdx;
int main(){
    cin >> n >> k;
    for(int i = 0,x; i < n; i++) {
        cin >> x;
        if(x == 1) lionIdx.push_back(i);
    }

    int lsize = lionIdx.size();

    for(int i = 0; i <= lsize - k; i++){
        length = min(length, lionIdx[i + k - 1] - lionIdx[i] + 1);
    }

    if(length == 0x3f3f3f3f) cout << -1;
    else cout << length;
}