[Python] boj no. 1806 : 부분합

Problem

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

Idea

문제를 요약하면 연속된 수열이 부분합이 S 이상인 수열의 최소 길이 값을 찾는 것이다. 우선 부분합이 S 이상인 수열은 다음과 같은 방법으로 찾을 수 있다.

1. 현재 수열의 부분합이 S 미만이면 다음 오른쪽 값을 수열에 포함한다.
2. 현재 수열의 부분합이 S 이상이면 해당 수열을 집합에 추가하고 가장 왼쪽 값을 수열에서 제외한다.

이를 구현하기 위해 투 포인트 알고리즘을 활용하였다. 현재 수열의 가장 왼쪽 수의 주소를 lp, 가장 오른쪽 수의 주소를 rp로 놓고 다음의 과정을 거쳐 수열의 최소 길이를 찾아내었다.

1. 현재 수열의 부분합이 S 미만이면 rp++
2. 현재 수열의 부분합이 S 이상이면 부분합이 S 미만이 될때까지 최소 길이 값을 최신화 시키면서 lp++를 반복.
3. 1~2의 과정을 rp >= N 이 될때까지 반복.

Code

import sys

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

sum = 0
lp, rp = 0, 0
length = sys.maxsize

while rp < N:
    sum += sequence[rp]
    
    while sum >= S:
        length = min(length, rp-lp+1)
        sum -= sequence[lp]
        lp += 1

    rp += 1

if length == sys.maxsize:
    print(0)
else:
    print(length)

Comment