[백준/python] 1806번 부분합

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

1806번: 부분합

 

코드

from itertools import accumulate
from collections import deque

input = __import__('sys').stdin.readline
n, s = map(int, input().split())
li = list(accumulate(list(map(int, input().split()))))
li = deque(li)
li.appendleft(0)
mn = float('inf')
l, r = 0, 1

while r <= n:
    if li[r] - li[l] >= s and l < r:
        mn = min(mn, r - l)
        l += 1
    else:
        r += 1

if mn == float('inf'): print(0)
else: print(mn)

 

풀이

주어진 수열의 부분합이 특정값이 넘을 때, 그중 가장 길이가 짧은 것의 길이를 찾으면 된다.

우선, 주어진 시간의 길이가 짧기 때문에 빠른 입력을 사용해준다.

그리고 나서 파이썬 자체에서 지원하는 누적합 라이브러리를 사용하면 코드의 길이를 줄일 수가 있다.

가장 짧은 길이의 누적합을 탐색하기 위해서는 투포인터 알고리즘을 활용하면 된다.

투포인터 알고리즘을 활용하기 위해서 deque 라이브러리를 불러와주고 최저값을 저장하는 mn 변수에 inf를 저장하여

최종값이 inf일 경우 0을 출력하고 그렇지 않을 경우 최소값을 그대로 출력해주면 된다.