[백준 BOJ / Python] 13422번 도둑

문제

마을에는 N개의 집이 순서대로 원 형태로 서로 이웃해 있다. 각 집에는 돈이 보관되어 있으며, 이 돈의 양은 숫자로 표시된다. 도둑은 M개의 연속된 집에서 돈을 훔치기로 하였고, 만약 도둑이 훔친 돈의 총액이 K원 이상이 되면 방범장치가 작동하여 붙잡히게 된다. 따라서 도둑이 붙잡히지 않고 무사히 마을을 빠져나가기 위해 돈을 훔칠 M개의 연속된 집을 선택하는 방법의 수를 구해야 한다.

n=8, m=3, k=15 일 때의 경우의 수

 

풀이

• 이 문제에서 중요한 점은 집들이 원 형태로 이웃했다는 점이다.

n=8, k=4 일 때

• 원의 형태이기 때문에 위 그림의 오른쪽 이미지들처럼 7번 집을 지나 0번 집까지 연속으로 돈을 훔치는 것이 가능하다.
• 도둑질을 시작하는 집을 기준으로 0부터 n-1까지 m칸씩 합계를 구해, 방범 장치가 울리지 않는 크기가 총 몇 가지 있는지 구하면 된다.
• 주의해야 할 것은 훔칠 집 개수(m)가 마을 전체 집 개수(n)와 같을 때이다. (n=m)
• 만약 m이 n과 같다면 모든 집을 터는 경우의 수 1개 밖에 없기 때문이다.
  • 0에서 7까지 집들을 훔쳤을 때와 1에서 한바퀴를 돌아 0까지 집들을 훔쳤을 때는 동일하다.
• 이 때는 방범 장치가 작동하지 않아 모든 집에서 돈을 훔치거나 도둑질을 포기하는 방법 밖에 없다.

if n == m:
    if sum(houses) < k: # 훔친 금액 < 방범 장치 작동 비용 
    	ans = 1 # 전체를 훔치는 한 가지 경우만 있다.
    else:
    	ans = 0 # 방법 장치가 작동함으로 아무 것도 훔칠 수 없다.

 

Python 코드

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    # 총 집 개수, 연속으로 훔질 집 개수, 방범 장치 작동 최소 비용
    n,m,k = map(int, input().split())
    # 돈의 양
    houses = list(map(int, input().split()))
    
    if n == m:
        if sum(houses) < k:
            ans = 1
        else:
            ans = 0
    else:
        houses += houses
        ans = 0
        cur = sum(houses[:m])
        for i in range(n):
            if cur < k:
                ans += 1
            cur -= houses[i]
            cur += houses[i+m]

    print(ans)

* 메모리를 줄여야하는 상황이라면, houses는 그대로 두고 cur에 더할 때 cur += houses[(i + m) % n]을 사용할 수 있다.

 

문제출처

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