[백준] 1806 부분합 in Python : 투 포인터

1. 정직한 나의 dp 풀이 

시간초과가 났다 

# 1806 부분합

n, s = map(int, input().split())
array = list(map(int, input().split()))
INF = int(1e9)
dp = [INF] * (n+1)

for i in range(n):
    temp = array[i]
    count = 1
    for j in range(i+1, n):
        if temp >= s:
            dp[i] = count
            continue
        else:
            temp += array[j]
            count += 1

print(min(dp))

2. 유형을 보니까 투포인터 알고리즘을 사용하는 것이다. 

먼저 0번째 인덱스부터 현재 인덱스까지의 원소들의 합을 저장해 놓은 sum_array를 새로 만들어야 한다. 

그리고 sum_array에서 start = 0 , end = 1 으로 인덱스를 설정한다. 

sum_array[end] - sum_array[start] 가 부분합이 되며, 이 부분합이 S이상인지 확인한다. 

S 이상이라면 시작점이 'start == 0'인 경우는 확인한 것이므로, start 를 한칸 뒤로 이동시킨다. 

S 이하라면 아직 우리는 0 부터 시작하는 순열에 원소를 더 더해주어야 한다는 의미이므로 end 를 뒤로 이동시킨다. 

단, end 가 n 에 이미 도달했다면, start를 이동시켜야 sum_array의 index 초과를 하지 않는다. 

# 1806 부분합
INF = int(1e9)
n, s = map(int, input().split())
array = list(map(int, input().split()))
sum_array = [0]*(n+1)
for i in range(1, n+1):
    sum_array[i] = sum_array[i-1] + array[i-1]

# 투포인터
start = 0
end = 1
count = INF

while start < n:
    if sum_array[end] - sum_array[start] >= s:
        if end - start < count: # array[end] 값을 포함하지 않으므로 end - start 가 맞다 
            count = end - start
        start += 1 # start 지점 이동
    else:
        if end != n:
            end += 1
        else: # end == n end가 가장 마지막 인덱스에 있을 때
            start += 1


if count == INF: # 합 s 불가능
    print(0)
else:
    print(count)