1806_부분합

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

1806번: 부분합

 

 

 

이역시 투포인터로 풀 수 있었다!

 

단 이전까지는 start포이터와 end 포인터가 끝에서 시작했는데 이번에는 둘다 시작점에서 출발하게 하는것이 달랐다.

 

10 15
5 1 3 5 10 7 4 9 2 8

 

 

먼저 start포인터와 end 포인터를 둘다 0이라 생각하고 시작한다.

 

그리고 두 포인터 가 지칭하는 사이의 값들을 더한게 S보다 작다면 end 포인터를 증가시키고, 그렇지 않다면 start포인터를 증가시키면 된다.

 

즉,

 

5

5,1

5,1,3

5,1,3,5

5,1,3,5,10

1,3,5,10

3,5,10

...

 

이런 방향으로 계산해야 하는 값이 바뀔 것이다.

 

처음에는 이를 슬라이싱을 이용한후 sum 함수로 계산했는데 자꾸 시간초과에 걸렸다. 그래서 그냥 sum값과 len값을 그때그때 계산해 주었다.

 

또 주의할점이 하나있는데, 탐색을 끝낼 조건이다. 난 처음에 end 포인터가 맨 끝에 다다르면 종료되게 했었는데 잘 생각해보면 start포인터가 끝에 도착해야 완전히 탐색이 끝난다는것을 알 수 있다.

 

 

 

import sys
N,S = map(int,sys.stdin.readline().split())
lst = list(map(int,sys.stdin.readline().split()))

start,end = 0,1
result =int(1e9)
SUM,LEN = lst[0],1
while start < N:
    if SUM >= S:
        if LEN < result:
            result = LEN
        SUM -= lst[start]
        LEN -=1
        start +=1
    elif end < N:
        SUM += lst[end]
        LEN +=1
        end += 1
    else:
        start+=1
print(result if result != int(1e9) else 0)