[백준] 15565 - 귀여운 라이언

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

15565번: 귀여운 라이언

 

K와 N 모두 1 이상 10^6 이하인 구간이므로, 일반적인 투 포인터를 사용하면 TLE가 날 수 있다.

 

그래서 라이언 인형의 좌표만 따로 저장하였다.

 

예를 들어 예제 입력 1에서

1 2 2 2 1 2 1 2 2 1 => 0 4 6 9

이런 식으로 라이언의 좌표만 따로 저장하면 O(N) 시간에 답을 구할 수 있는 것이 자명하다.

 

이후 left = 0, right = k - 1로 두고 탐색하면 된다.

 

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

int n, k;
vector<int> v;

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		if (a == 1)
			v.push_back(i);
	}

	if (v.size() < k)
		cout << -1;
	else
	{
		int left = 0, right = k - 1;
		int ans = 1000000000;
		while (right < v.size())
		{
			ans = min(ans, v[right] - v[left] + 1);
			left++;
			right++;
		}
		cout << ans;
	}
}