[백준 13422] 도둑 (Python)

www.acmicpc.net/problem/13422

13422번: 도둑

 

문제풀이

N, M, K, arr : 입력값

left, right : 투 포인터

tmp : 현재 훔친 돈의 합

q : 현재 수열

 

투 포인터(Two-Pointer) 를 이용하여 쉽게 해결할 수 있다. 정확히는 투 포인터보다는 슬라이딩 윈도우 문제라고 생각한다. 

N == M 일때 예외가 존재하므로 이를 처리해줘야 한다.

ex )

1

3 3 5

1 1 1

이 경우 정답은 1이 나와야 한다. (어느 인덱스를 선택하든 모두 같은 경우이기 때문)

 

1. right를 증가시키면서 현재 수열의 길이가 M일때까지 현재 훔친 돈(tmp)에 각 원소를 더한다.

 

2. 1의 과정을 마치고 현재 훔친 돈이 K 보다 작을 경우 ans 를 증가한다.

 

3. 현재 수열의 가장 좌측 원소를 빼고 left를 증가한다.

 

코드를 보면 쉽게 이해할 수 있다.

 

코드

import sys
from collections import deque

if __name__ == '__main__':
    for _ in range(int(input())):
        N, M, K = map(int, sys.stdin.readline().split())
        arr = list(map(int, sys.stdin.readline().split()))
        right = 0
        tmp, ans = 0, 0
        q = deque()
        for left in range(N):
            while right < N + M - 1 and len(q) < M:
                q.append(arr[right % N])
                tmp += arr[right % N]
                right += 1
            if tmp < K: ans += 1
            q.popleft()
            tmp -= arr[left]
            left += 1
            if N == M: break
        print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!