[Python] BOJ 1806 - Subsequence(부분합)

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

1806번: 부분합

# N이 최대 10만이므로 완전탐색으로 구하는것은 시간초과가 난다.

   따라서, 투 포인터 알고리즘을 사용하여 풀었다.

 

1. 처음 부분합 s에 nums[0]을 넣어준다. (첫번째 숫자 그 자체로 S를 넘을 수 있기 때문에)

   그리고 포인터 i, j를 0으로 초기화해준다.

 

2. 만약 현재 부분합 s가 구하고자 하는 S보다 같거나 크면 왼쪽 포인터가 가리키는 nums의 수(nums[i])를

    s에서 빼주고, 현재 j와 i사이가 ans보다 작으면 ans를 갱신해준다. 

    그리고 왼쪽 포인터 i를 1 증가

 

3. s가 S보다 작으면 오른쪽 포인터 j를 1 증가시킨다.

    만약 j가 N이면 오른쪽 끝까지 포인터가 간 것이므로 break를 해주고

    아니면 s에 nums[j]를 더해준다.

 

4. ans의 최댓값은 10만이므로 초기값을 100,001로 설정하고 마지막까지 ans가 100,001이면

    0을 출력하고, 아니면 ans를 출력한다.

 

N, S = map(int,input().split())
nums = list(map(int,input().split()))
i, j = 0, 0
s = nums[0]
ans = 100001

while True:
    if s >= S:
        s -= nums[i]
        ans = min(ans, j - i + 1)
        i += 1
    else:
        j += 1
        if j == N:
            break
        s += nums[j]

print(0) if ans == 100001 else print(ans)

(solved.ac 티어: 골드 4)