[Python] 백준/BOJ 13422번: 도둑 (Gold 4)

💻 Problem

문제 보러 가기

 

다음 그림과 같이 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개의 연속된 집을 고르는 방법의 수를 출력하는 프로그램을 작성하시오.

 

💡 Approach

위 이미지를 예시로 들면 index 0 ~ 7이 있다.

각 인덱스부터 시작해서 M개의 집에 있는 돈의 양이 K 미만이면 훔칠 수 있는 경우이다.

훔칠 수 있는 방법의 수를 구하는 문제이다.

 

먼저 시작부터 M개의 집에 있는 돈의 양을 구한다. (total)

슬라이딩 윈도우 기법으로 계속 범위를 조정한다.

범위가 M이면 M개의 집 중 처음 값을 빼고 범위 바로 다음 값을 더하면 된다.

 

다만 처음에 N == M인 경우를 생각하지 못해서 틀렸었다.

예를 들어, N = M = 5라면 몇 번째 인덱스에서 시작하든 같은 집 조합으로 훔친 것이 되어 버린다.

따라서 N == M일 때는 1가지거나 0가지일 수밖에 없다.

 

✏️ Solution

import sys
input = sys.stdin.readline

def steal():
    if N == M:
        return int(sum(house) < K)
    
    total = sum(house[:M]) # 훔친 돈의 양
    cnt = int(total < K)# 돈을 훔치는 방법의 가짓수

    for i in range(1, N):
        # 현재 범위의 이전 값을 빼고 다음 값을 더하기
        total = total - house[i - 1] + house[(i + M - 1) % N]
    
        if total < K:
            cnt += 1
    
    return cnt

T = int(input())
for _ in range(T):
    # 마을에 있는 집의 개수 N(1 ≤ N ≤ 100,000)
    # 도둑이 돈을 훔칠 연속된 집의 개수 M(1 ≤ M ≤ N)
    # 자동 방범 장치가 작동하는 최소 돈의 양 K(1 ≤ K ≤ 1,000,000,000, K는 정수)
    N, M, K = map(int, input().split())

    # N개의 집에서 각각 보관중인 돈의 양
    house = list(map(int, input().split()))
    
    print(steal())