PS/문제풀이

백준 1806 부분합 Python

중규리 2024. 1. 28. 12:49

🐸 문제 정보

 

1806번: 부분합

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

www.acmicpc.net

 

🤖 알고리즘

누적합, 투포인터

 

⏱️ 풀이 시간

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)