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

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

15565번: 귀여운 라이언

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, k;
	cin >> n >> k;
	
	vector<int> rion_position;
	
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		if(x == 1) rion_position.push_back(i);
	}
	
	if(rion_position.size() < k){
		cout << -1 << endl;
		return 0;
	}
	
	int ans = 1000001;
	for(int i = 0; i <= rion_position.size() - k; i++){
		ans = min(ans, rion_position[i + k - 1] - rion_position[i] + 1);
	}
	cout << ans << endl;
	return 0;
}

 

입력 배열에서, 라이언이 위치한 인덱스의 위치를 저장하는 별도의 배열을 만든다.

 

이 인덱스를 K개 조사하는 슬라이딩 윈도우를 만들어준다.

 

아래 그림은 K개의 라이언이 존재하려면 1~7까지 총 7개의 인형이 필요한 경우이다.

 

아래 그림은 K개의 라이언이 존재하려면 5~10까지 총 6개의 인형이 필요한 경우이다.

 

이처럼 윈도우를 이동하며 라이언이 K개 존재할 수 있는 인형 수를 찾아, 최소 개수를 출력한다.