[백준/Python] 부분합

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

1806번: 부분합

생각보다 어렵지 않은 투포인터 문제여서 자신있게 제출했지만 시간초과...^^

이유는 sum()을 사용한 것 때문! 부분합 리스트를 저장해두는 방법을 사용하여 해결했다

n, s = map(int, input().split())
nums = list(map(int, input().split()))
l, r = 0, 1 # 투 포인터
ans = 1e9 # 최소 길이
sum_n = [0] * (n+1) # 부분합 리스트

for i in range(1, n+1):
    sum_n[i] = sum_n[i-1] + nums[i-1]

while l < n+1 and r < n+1:
    result = sum_n[r] - sum_n[l] # l부터 r까지의 합

    if result >= s: # 합이 s이상이면 최소길이를 갱신 왼쪽 포인터 이동
        ans = min(ans, r-l)
        l += 1
    else: # 합이 s미만이면 오른쪽 포인터 이동
        r += 1

print(0) if ans == 1e9 else print(ans)

1. 투 포인터 변수와 부분합 리스트를 생성한다

2. 부분합 리스트를 구한다

3. 투 포인터가 범위를 벗어나지 않을 때까지 최소길이를 구한다

4. 먼저 l부터 r까지의 합인 result를 구한다

5. result가 s 이상이면 최소길이를 갱신하고 l을 이동시킨다

6. result가 s 미만이면 r을 이동시킨다

7. 문제의 조건에 따른 결과를 출력한다