백준 1806 부분합 Python

🐸 문제 정보

1806번: 부분합

 

🤖 알고리즘

누적합, 투포인터

 

⏱️ 풀이 시간

12.12m

 

📝 풀이

누적합으로 풀면 간단하지만, 구할 수 없는 경우 0 출력 처리 때문에 약간의 시간 낭비를 했다.

주어진 입력 리스트를 누적합으로 만들고,

투포인터를 돌면서 아래 조건에 따라 처리하면 된다.

1. start와 end 사이의 합이 s보다 크거나 같다면, 길이에 대해 최소값 처리를하고 start를 뒤로 한 칸 이동
2. start와 end 사이의 합이 s보다 작다면, end를 뒤로 한 칸 이동

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline
INF = sys.maxsize

n, s = list(map(int, input().rstrip().split()))
prefix = [0] + list(map(int, input().rstrip().split()))
for i in range(1, n + 1):
    prefix[i] += prefix[i - 1]
res = INF

st, en = 0, 1
while True:
    if (en == n) and ((prefix[en] - prefix[st]) < s):
        break
    if s <= (prefix[en] - prefix[st]):
        res = min(res, en - st)
        st += 1
    else:
        en += 1

if res == INF:
    print(0)
else:
    print(res)