[Python] 백준 1806 - 부분합 문제 풀이

Overview

BOJ 1806번 부분합 Python 문제 풀이
분류: Two Pointers (투 포인터)


문제 페이지

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


풀이 코드

from sys import stdin


INF = 1_000_000_001


if __name__ == "__main__":
    def input():
        return stdin.readline().rstrip()

    n, s = map(int, input().split())
    seq = list(map(int, input().split()))

    left, subsum, ans = 0, 0, INF
    for right in range(n):
        subsum += seq[right]

        while left <= right and subsum >= s:
            ans = min(right - left + 1, ans)
            subsum -= seq[left]
            left += 1

    print([0, ans][ans != INF])

투포인터를 이용하여 조건을 만족하는 부분 수열 길이의 최솟값을 구한다.

좋은 웹페이지 즐겨찾기