부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이 구하기.
입력 | 출력 |
---|---|
10 15 5 1 3 5 10 7 4 9 2 8 | 2 |
: 인덱스를 활용하여 while문에서 sum함수로 부분합을 구하자. -> sum함수를 사용하면 시간초과
투포인터 알고리즘을 사용할 수 있다.
- while문 활용
- start, end 두개의 포인터를 두고 이를 인덱스로 사용한다.
- 처음에는 start, end = 0, 0
- 부분합이 주어진 수보다 작으면 부분합에 end번째 값 더하기 & end ++
- 부분합이 주어진 수 이상이면 end-start로 길이를 구하고 최소인지 확인 & start번째 값 빼기 & start ++
- end가 수열의 길이와 같을 때 반복문 탈출.
n, s = map(int, input().split())
nums = list(map(int, input().split()))
start, end = 0, 0
mini = 1e9
sumi = 0
while True:
if sumi>=s:
mini = min(mini, end-start)
sumi -= nums[start]
start += 1
elif end == n:
break
else:
sumi += nums[end]
end += 1
if mini == 1e9:
print(0)
else:
print(mini)