[백준-파이썬] 13422: 도둑

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

풀이 🐸

N개 집이 원형으로 쭉~ 놓여있고 각각 집에는 돈이 있다. 도둑은 연속된 집 M개를 턴다.(각 집에 있는 돈을 다 가져간다) 이 돈이 K 미만이어야만, 도둑이 안전하게 돌아갈 수 있다. 도둑이 무사히 돌아갈 수 있으면서, M개 집에서 도둑질할 때 그 경우의 수를 구해야 한다.

투 포인터로 쭉~ 봐줬다.
도둑질 당하기를 시작하는 집, 끝나는 집을 left, right로 뒀다. 그 집들에서 훔친 돈을 stolen_money로 뒀다. 맨 처음에는 left부터 right까지의 집에 있는 돈을 다 더해서 stolen_money를 초기화했다. 그 후에 한 집씩 옮기면서 stolen_money를 봤다. 한 집씩 옮길 때 left집의 돈을 stolen_money에서 빼고, right 집의 돈을 더했다. stolen_money가 K이하이면 ans에 1을 더하고, 아니면 넘어갔다.

집이 원형인데 우리는 houses 리스트에 일자로 넣어줬다. right가 houses 리스트의 앞쪽으로 가게 될 수도 있으니까 if right>=N: right = right - N을 해줬다.

틀렸던 이유🌸

투 포인터로 무난하게 풀려서 '이게 왜 골드 4지?'라는 생각을 했는데, 그 순간 틀렸다...
N==M인 경우를 생각해야 한다!!!

코드 👩‍💻

import sys

input = sys.stdin.readline
MIIS = lambda: map(int, input().split())

T = int(input())
for _ in range(T):
    N, M, L = MIIS()
    houses = list(MIIS())

    ans = 0

    left, right = 0, M - 1
    stolen_money = sum(houses[left:right + 1])

    if N == M:
        if stolen_money < L:
            ans += 1
    else:

        while left < N:
            if stolen_money < L:
                ans += 1
            stolen_money -= houses[left]
            right += 1
            if right >= N:
                right = right - N
            stolen_money += houses[right]
            left += 1

    print(ans)