[백준]#1806 Python

백준 1806번 부분합

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

시간초과 코드

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
nums = [0] + list(map(int, input().split()))
partial_sum = [0] * (N+1)

for i in range(1, N+1):
    partial_sum[i] = partial_sum[i-1] + nums[i]
    
ans = 100000
for i in range(1, N+1):
    if partial_sum[i] >= S:
        level = 0
        diff = 0
        while diff <= S:
            level += 1
            if level < i:
                diff = partial_sum[i] - partial_sum[i - level]
            else:
                continue
        
        ans = min(ans, level)


if ans == 100000:
    print(0)
else:
    print(ans)

어떤 부분합을 기준으로 삼을 것인지 + 해당 부분합의 원소 개수를 줄이기 위한 while문 사용 -> 이중 for 문을 사용해서 시간복잡도 O(N^)이 나온 것 같다,,, 다른 풀이를 찾아보니 투 포인터로 풀었던데 훨씬 효율적이다.

투 포인터 풀이

https://claude-u.tistory.com/393 <- 참고한 블로그

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

#먼저 0~n까지의 합을 구해줌
sum_A = [0] * (N + 1)
for i in range(1, N + 1):
    sum_A[i] = sum_A[i-1] + A[i-1]  
    
#투포인터 설정
answer = 1000001
start = 0
end = 1

#알고리즘 실행
while start != N:
    if sum_A[end] - sum_A[start] >= S:
        if end - start< answer:
            answer = end - start
        start += 1
        
    else:
        if end != N:
            end += 1
        else:
            start += 1

#답이 없을 경우 & 있을 경우
if answer != 1000001:
    print(answer)
else:
    print(0)

내 풀이로는 새로운 부분합[i]에서 차액을 비교할 때마다 새롭게 [i-level] 인덱스부터 시작해야 하는데, 투 포인터를 이용하면 그 과정을 생략할 수 있다 -> while 문 한번만 써도 됨.