[BOJ 15565] 귀여운 라이언 C++ 풀이

문제 링크

www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

귀여운 라이언 처분류

시간 제한 1 초

메모리 제한 256 MB

제출 1161

정답 464

맞은 사람 357

정답 비율 41.951%

문제

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)

둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)

출력

K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.

풀이

예제 입력	예제 출력
10 3 1 2 2 2 1 2 1 2 2 1	6

예제 입력을 예시로 설명을 진행하겠습니다.

 

시작 입력은 아래와 같은 그림으로, 각 인형의 정보가 입력됩니다.

라이언은 편의상 빨간색으로 표시하였습니다.

입력 배열

 

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

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

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

1, 2, 3, 4, 5, 6, 7번 위치의 인형이 필요하다

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

5, 6, 7, 8, 9, 10번 위치 인형이 필요하다.

위와 같이 윈도우를 이동하며 라이언이 K개 존재할 수 있는 인형의 수를 찾아, 최소 개수를 출력합니다.

 

 

위 설명을 아래와 같은 C++코드로 구현할 수 있습니다.

1. 라이언이 있는 인덱스를 저장하는 배열을 만들어서, 라이언의 위치만 저장한다.

2. 인덱스 배열에서, 연속한 K개를 검사하여 시작과 끝의 인덱스 차가 가장 작은것을 답으로 출력한다.

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

using namespace std;

int N, K;
vector<int> rion_position;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); // 입력 속도 향상

	int now;
	cin >> N >> K;

	for (int i = 1; i <= N; i++)
	{
    		//인형 정보를 받아온다.
		cin >> now;
        	// 인형이 라이언이면, rion_position에 현재 인덱스를 저장한다.
		if (now == 1) 
			rion_position.push_back(i);
	}

	int ans = 1000001;

	if (rion_position.size() < K)
	{
    		// 만약 라이언이 K개보다 적다면, 문제의 조건을 만족하지 못하므로
        	// -1을 출력후 종료한다
		cout << -1 << '\n';
		return 0;
	}

	for (int i = 0; i <= rion_position.size() - K; i++)
	{
    		// 인덱스 배열의 시작부터, K를 조사한다.
        	// 가장 큰 인덱스와, 가장 작은 인덱스 차를 계산하여 ans를 갱신한다.
		ans = min(ans, rion_position[i + K - 1] - rion_position[i] + 1);
	}
    
	cout << ans << '\n';
}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.