[백준알고리즘] 1806번: 부분합 -Python

[백준알고리즘] 1806번: 부분합 -Python

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

1806번: 부분합

이번 문제는 저번에 풀었던 2003번 수들의 합 문제와 유사했다.

다만, 여기서는 주어진 수 이상이면 됐고, 만족하는 부분 수열의 개수가 아닌 길이를 구하는 문제다.

 

따라서 마찬가지로 우선은 low pointer, high pointer 두 개를 사용했다.

반복문 안에서 조건들이 조금 달라졌을 뿐이다. tmp가 s보다 작아지거나 커지는 경우에 따라서 연산 횟수는 같겠지만 반복문을 한 번 더 돌기 전에 미리 포인터들을 옮겨주었다.

 

2003번 문제와 마찬가지로 일반 sum들을 모두 구하는 과정은 시간초과가 날 것이다. 2003번 보다 수열의 길이가 더 늘어났기 때문에 시간제한이 조금 늘어났다고 하더라도 O(N^2)를 만족하는 경우는 힘들 것 같다.

import sys
 
n, s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
 
lo, hi = 0, 1
tmp = arr[lo]
dist = sys.maxsize
 
while lo < n:
    if tmp >= s:
        dist = min(dist, hi-lo)
        tmp -= arr[lo]
        lo += 1
        
        if tmp < s and hi < n:
            tmp += arr[hi]
            hi += 1
    else: # tmp < s
        if hi >= n: # tmp < s
            break
            
        tmp += arr[hi]
        hi += 1
        
        if hi - lo >= dist:
            tmp -= arr[lo]
            lo += 1
 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다