백준 온라인 저지, 자료구조/180번: 부분합 (파이썬 / 백준 골드문제)

문제

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

문제 정의

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

접근 방법

1. 접근 방법
2. 큐를 통해 연속된 부분 수열을 구현한 뒤, 값을 하나씩 탐색하며 더해간다.
3. 만약 s이상이 된다면 길이를 저장하고, s보다 값이 작아질 때까지 큐에서 가장 끝에 있는 값을 뺀다.
4. 길이를 저장할 때는 현재 저장된 길이의 값과 큐의 길이 중 작은 것을 저장한다.

코드

# https://www.acmicpc.net/problem/1806
# 접근 방법
# 큐를 통해 연속된 부분 수열을 구현한 뒤, 값을 하나씩 탐색하며 더해간다. 
# 만약 s이상이 된다면 길이를 저장하고, s보다 값이 작아질 때까지 큐에서 가장 끝에 있는 값을 뺀다. 
# 길이를 저장할 때는 현재 저장된 길이의 값과 큐의 길이 중 작은 것을 저장한다.
from collections import deque
import sys

queue = deque([])
n, s = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))

total_sum = 0
min_distance = n+1
for x in array:
    total_sum += x
    queue.append(x)
    if total_sum >= s:
        while total_sum >= s:
            min_distance = min(min_distance, len(queue))
            x_ = queue.popleft()
            total_sum -= x_
                        
if min_distance == n+1:
    print(0)
else: 
    print(min_distance)