[BOJ 백준] 15565번 : 귀여운 라이언 (Python, 파이썬)

www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

 

슬라이딩 윈도우를 활용하는 문제였다.

 

문제에서 K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 구하라고 했으므로 일단 어피치는 신경쓰지말고 라이언 인형이 딱 K개가 되는 구간만 확인해주면 된다.

 

항상 K개가 되는 것을 확인해야 하므로 슬라이딩 윈도우를 활용할 수 있는 것이다.

 

예제에서 라이언 인형의 위치는 0, 4, 6, 9 이다. 라이언 인형은 총 4개가 있으며 K가 3이기 때문에 3개씩 묶어서 확인하면 된다.(윈도우의 크기가 3이다)

 

즉 아래와 같은 두개의 부분집합이 생긴다.

• (0, 4, 6)
• (4, 6, 9) 

부분집합의 맨 처음 인덱스를 start, 마지막 인덱스를 end라고 했을 때, 어피치 인형이 포함된 전체 인형의 개수는 list[end] - list[start] + 1 이다. 

 

윈도우의 크기를 K로 유지하며 한 칸씩 뒤로 밀어가며 계속 비교해나간다. 이 값이 최솟값이 되는 것이 가장 작은 연속된 인형들의 집합의 크기가 된다.  

 

 

소스코드

 

import sys

n, k = map(int, input().split())
dolls = list(map(int, input().split()))

answer = 100000000 # 최대 크기로 초기화

lion = [] # 라이언의 위치를 저장
for i in range(len(dolls)):
    if dolls[i] == 1:
        lion.append(i)
        
# 윈도우의 크기 = end - start = 라이언 인형의 개수
start = 0
end = k-1

if len(lion) < k: # 라이언의 개수가 K개 미만임 -> -1 출력 후 종료
    print(-1)
    exit(0)

while True:
    doll = lion[end] - lion[start] + 1 
    answer = min(answer, doll)
    if end == len(lion)-1: # 마지막까지 탐색 완료
        break
    # 윈도우의 크기를 K로 유지하며 한 칸씩 뒤로 민다
    start += 1 
    end += 1
print(answer)