백준 13422 : 도둑 (Python)

본문 링크

import sys
input=sys.stdin.readline

T=int(input())
for i in range(T):
    N,M,K=map(int,input().split())

    L=list(map(int,input().split()))

    if M!=N:
        for j in range(M-1):
            L.append(L[j])

    start= 0 ; end=M-1 ; count=sum(L[:M]) ; check=0

    if count<K:
        check+=1
    while end<len(L)-1:
        count-=L[start]
        start+=1 ; end+=1
        count+=L[end]
        if count<K:
            check+=1
    print(check)

📌 어떻게 접근할 것인가?

문제에서 M개의 연속된 집을 고르는 방법 이라는 조건이 주어졌을때
슬라이딩 윈도우를 사용할 생각을 했다.

그리고 까다로운 조건이 집은 원형을 이룬다는 것인데

단순하게 리스트 $L$ 에다가 $0$부터 $M$번째 인덱스를 append 해주면 1차원 배열으로 보나 원으로 보나 똑같이 모두 탐색 가능하게 된다.

이후 $while$ 문을 사용하여서 매번 도둑한 금액의 양이 $K$ 보다 작은지 체크해준다.

✅ 코드에서 주의해야할 부분

• $M==N$ 일때는 원형으로 보면안되기 때문에 리스트에 원소를 추가해주면 안된다.
• 처음에 $count$ 값이 $K$ 보다 작을수 있으므로 한번 체크해준다.