[Python/파이썬] 백준 13422번 도둑

13422번: 도둑

 

문제

다음 그림과 같이 N개의 집이 순서대로 이웃하여 세워진 마을이 있다.

위 그림은 N = 8인 경우 마을의 모습이다. 위 그림과 같이 각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있다. 예를들면 3이 적힌 집은 9, 4가 적힌 집과 이웃해 있으며, 5가 적힌 집은 6, 7이 적힌 집과 이웃해 있다. 이 마을 사람들은 각자 자신의 집에 돈을 보관한다. 위 그림에서 각 집에 적혀 있는 숫자는 집마다 보관 중인 돈의 금액을 나타낸다. 어느 날 이 마을에 도둑이 들었다. 도둑은 이 마을에서 어떻게 도둑질을 할까 잠시 고민하다가, 빠르게 돈을 훔치고 달아나기 위해 M개의 연속된 집에서 돈을 훔치되, 돈을 훔칠 때는 각 집에 보관중인 돈을 전부 훔치기로 했다. 예를 들어 M = 3일 때, 위 그림에서 순서대로 3, 4, 7의 돈을 보관중인 집에서 총 14의 돈을 훔친 후에는 더 이상 돈을 훔치지 않고 달아나야 한다. 또 다른 예로는 순서대로 5, 6, 4의 돈을 보관중인 집에서 총 15의 돈을 훔친 후에는 달아나야 한다. 그러나 만약 도둑이 이 마을에서 총 K원 이상의 돈을 훔친다면 자동 방범장치가 작동하여 도둑은 바로 붙잡히게 된다. 예를 들어 M = 3, K = 15인 경우 위 그림에서 순서대로 3, 4, 7의 돈을 보관중인 집에서 도둑질을 한다면 총 도둑질한 돈이 14가 되어 붙잡히지 않고 달아날 수 있지만, 순서대로 5, 6, 4의 돈을 보관중인 집에서 돈을 훔친다면 총 도둑질한 돈은 15가 되고, 방범장치가 작동하여 도둑은 붙잡히게 된다.

마을을 이루고 있는 집의 개수 N, 도둑이 돈을 훔쳐야 할 연속된 집의 개수 M, 자동 방범장치가 작동하는 최소 돈의 양 K와 각 집에서 보관 중인 돈이 순서대로 주어질 때, 도둑이 붙잡히지 않고 무사히 마을을 빠져나가기 위해 돈을 훔칠 M개의 연속된 집을 고르는 방법의 수를 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마을에 있는 집의 개수 N(1 ≤ N ≤ 100,000), 도둑이 돈을 훔칠 연속된 집의 개수 M(1 ≤ M ≤ N), 자동 방범 장치가 작동하는 최소 돈의 양 K(1 ≤ K ≤ 1,000,000,000, K는 정수)가 공백으로 구분되어 주어진다. 테스트 케이스의 둘째 줄에는 N개의 집에서 각각 보관중인 돈의 양이 시계방향 순서대로 공백으로 구분되어 주어진다. 돈의 양은 각 집이 이웃해 있는 순서대로 주어진다. 첫 번째 집과 마지막 집 또한 이웃하기 위해 입력의 첫 번째와 마지막이 서로 연결되어 있다고 가정하며, 각 집에서 보관 중인 돈의 양은 1이상 10,000이하의 정수이다.

출력

출력은 표준 출력을 사용한다. 입력 받은 데이터에 대해, 도둑이 자동 방범장치에 붙잡히지 않도록 연속된 M개의 집에서 돈을 훔치는 방법의 가짓수를 한 줄에 1개씩 출력한다.

코드

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    money = list(map(int, input().split())) * 2
    # 누적합
    acc = [0] * (n*2)
    for i in range(1, 2*n):
        acc[i] = acc[i-1] + money[(i-1) % n]
    if n == m and (acc[n]-acc[0]) < k:
        print(1)
        continue
    ans = 0
    for i in range(n):
        if (acc[i+m]-acc[i]) < k:
            ans += 1
    print(ans)

돈을 훔칠 집의 개수가 m개로 고정되어 있어서 슬라이딩 윈도우 알고리즘을 이용하여 코드를 작성하는 것은 쉬웠지만 n과 m의 값이 같을 때를 고려해주지 못해서 조금 시간이 걸렸다. 예를 들어 입력값이 아래와 같을 때

 

1
3 3 4
1 1 1

이 테스트케이스의 정답은 1이다. 그렇지만 n == m일 때를 고려해주지 않는다면 위의 결과값은 3이 나온다. 이 경우를 해결해주니 통과할 수 있었다.