[C++/백준] 15565번: 귀여운 라이언

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

15565번: 귀여운 라이언

• 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include<cmath>
#define LL long long
using namespace std;

int main() {
	
	vector <int> arr;
	int n;
	int k;
	cin >> n >> k;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num == 1) {
			arr.push_back(i);
		}
		
	}
	if (k > n) {
		cout << -1 << endl;
	}
	else if (arr.size() < k) {
		cout << -1 << endl;
	}
	else {
		int ans = arr[arr.size() - 1] - arr[0] + 1;

		for (int i = 0; i < arr.size() - k+1; i++) {
			ans = min(ans, arr[i + k-1] - arr[i] + 1);
		}
		cout << ans << endl;
	}

	return 0;
}

• 알고리즘 분류 : 슬라이딩 윈도우
• 문제해설

1과 2로만 이루어진 배열이라는 점에서 단순한 해결방법이 있다는 생각을 하면 좀더 쉽게 접근할 수 있었을 것 같다. 

일단 접근 방법을 알면 그 다음부터 구현은 쉽기 때문에 접근 하는 방법은 다음과 같다.

라이언 인형이 k개 이상이지만 최소 길이를 구하라고 했으므로 k개까지만 구하면 된다.

연속된다고 했기 때문에 라이언 인형이 있는 처음 시작 인덱스과 마지막 인덱스까지 길이를 구하면 된다.

이제 배열을 탐색해야겠다고 생각하면 되는데 투포인터를 사용할 경우 라이언이 아닌 2를 계속 확인해야하는게 거슬린다면 접근에 가까워진다. 따로 배열을 만들어 1이면 그 인덱스를 저장한다. 이렇게 하면 인형의 정보를 한번만 확인하고 슬라이딩 윈도우로 따로 만든 배열을 k만큼의 길이로 탐색하여 가장 작은 길이를 갱신하면 된다.