백준 15565. 귀여운 라이언

tose33 2023. 10. 6. 12:44

15565번: 귀여운 라이언

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

www.acmicpc.net

처음에 보자마자 이분탐색이 생각나서 이분탐색으로 풀었다.

이분탐색으로 집합 크기를 정하고, 그 크기 내에 1이 K개 이상있는지 슬라이딩 윈도우로 판단한다.

풀고나서 다른 분들 코드를 봤는데 다른 방법으로 많이 풀었다.

먼저 라이언의 인덱스를 저장한다.

예제의 경우 0,4,6,9 가 라이언의 인덱스다.

3개의 라이언이 필요하기 때문에 3개씩 묶어서 끝인덱스-첫인덱스+1을 하면 길이가 된다.