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

문제

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

15565번: 귀여운 라이언

---

문제 요약

1과 2로 이루어진 n개의 수열이 주어질 때, 1을 k개 갖는 가장 작은 부분 수열의 길이를 출력한다.

---

코드

#include <iostream>
#include <vector>

#define MAX_N 10000
#define INF 1000000000
using namespace std;

int n, k;

int res = INF;

vector<int> lions; // 라이언 인형들의 인덱스 정보 저장

int main() {

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (num == 1) {
			lions.push_back(i);
		}
	}

	int left = 0;
	int right = k - 1;

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


	while (right < lions.size()) {
		res = min(lions[right] - lions[left] + 1, res);
		// cout << left << " " << right << " " << res << "\n";
		left++;
		right++;
	}

	cout << res;
}

---

코드 설명

1. 입력 받은 수열(배열)에서 1의 인덱스 좌표를 따로 저장하는 벡터를 생성한다.

+ 1의 개수가 k개보다 작다면 -1을 출력한다.

 

2. 수열의 가장 왼쪽부터 오른쪽으로 1칸씩 움직이며 1을 k개 갖는 부분수열의 길이를 구하고, 최소값을 갱신한다. 

+ 오른쪽으로 더 이상 움직일 수 없을 때까지 이동한다.

 

3. 최소값을 출력한다.