[BOJ] 1806. 부분합

📌 문제 제목

문제 링크: BOJ 1806

---

🗒️ 문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 있을 때, 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것을 구하여라.

시간 제한: 0.5초

메모리 제한: 128MB

10 <= N < 100,000

0 < S <= 100,000,000

---

💡 문제 해결 아이디어

• 시간 제한이 0.5초이고 N이 최대 100,000개 이므로 O(N)의 시간복잡도를 가지는 알고리즘을 사용
• 연속된 수들의 부분합을 구하는 문제이므로 투 포인터 사용
• st를 0으로 잡고 부분합이 S 이상일 때 까지 en을 증가 + total에 부분합을 더하기
• 처음 total이 S 이상일 때 answer을 비교 후 갱신
• total에 seq[st] 감소

---

⌛️ 시간 복잡도

• O(N)
• st는 최대 N번 반복
• en은 전체 루프 동안 N번까지 수행
• O(2N) -> O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
seq = list(map(int, input().split()))

en = 0
total = 0
answer = float("inf")

for st in range(N):
    while en < N and total < S:
        total += seq[en]
        en += 1

    if total >= S:
        answer = min(answer, en - st)

    total -= seq[st]

print(answer if answer != float("inf") else 0)