백준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개씩 출력한다.

---

투 포인터 문제인데 그냥 브루트 포스 처럼 풀어서 시간초과가 났고 이를 해결하기위해 투포인터로 풀었다.

한집을 넘어가면서 합에서 앞에꺼는 빼고 뒤에꺼는 더하는 방식을 사용

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N, M, K = map(int,input().split())
    
    homes = list(map(int,input().split()))
    
    cnt = 0
    # N과 M이 같다면
    # 다 더해서 확인
    if N == M:
        sum_money = sum(homes)
        if sum_money < K:
            cnt += 1
    else:
        # 인덱스 넘는것을 방지하기 위해서
        homes += homes
        # 처음 M개 집 합
        sum_money = sum(homes[:M])
        i = 0
        
        while i < N:
            if sum_money < K:
                cnt += 1
            # 앞에 집은 빼고 뒤에 집은 더하는 방식
            sum_money = sum_money - homes[i] + homes[i+M]
                  
            i += 1
            
    print(cnt)