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

Eunho Bae·2022년 4월 8일
0

백준

목록 보기
23/40

문제 링크


아이디어

설명

2 2 1 2 1 2 2 1 2 2 1 (크기 : 11)
k=3인 경우 라이언 인형이 3개 이상 존재하는 '가장 작은' 연속된 집합의 크기를 구하라는 문제다.
여기서 키 포인트는 '가장 작은'이 된다.

위 배열의 경우 만약 '가장 큰' 연속된 집합의 크기를 구하는 문제였다면 배열 전체가 답이 된다. 하지만 가장 작은 집합의 크기를 구하라고 했기 때문에 범위가 1 2 1 2 2 1로 좁혀진다.

결국 처음 등장하는 1부터 마지막 k번째로 등장하는 1의 위치를 구해서 범위를 구하면 그것이 답이 되는 문제이다.

코드 설명

입력 배열을 담을 v와 1의 위치 인덱스를 담을 ones를 선언한다.
입력 받을 때마다 1이라면 그 위치를 push해준다.

만약 k보다 1의 개수가 작으면 답을 구할 수 없기 때문에 바로 리턴을 때려준다.


제출코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	vector<int> v(n);
	vector<int> ones;

	for (int i = 0; i < n; i++) 
	{
		cin >> v[i];
		if (v[i] == 1)
			ones.push_back(i);
	}

	int ans = 1000001;

	if (ones.size() < k)
	{
		cout << -1;
		return 0;
	}

	for (int i = 0; i <= ones.size() - k; i++)
		ans = min(ans, ones[i + k - 1] - ones[i] + 1);

	cout << ans;

	return 0;
}
profile
개인 공부 정리

0개의 댓글