문제
접근
투 포인터 문제이다.
start, end를 두고 원하는 값 S 보다 작으면 end에 위치한 원소를 더하고 end를 한칸 움직인다.
S보다 커진다면 start에 있는 값을 빼고 start를 한칸 움직인다.
이를 배열의 끝까지 반복하며 S를 만족시키는 end-start 중 최소를 찾는다.
종료 조건을 만들다가 코드가 조금 난잡해졌다.
처음에는 end와 start를 이용해서 종료 조건을 만들려고 했는데, 잘 모르겠다.
end가 끝까지 도달했을 때, 종료되어버리면 틀리는 케이스들이 생긴다.
end가 끝에 도달했을 때 nowSum이 S보다 큰 경우에는 계속 수행하며 start를 더 조정해주도록 하였다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
input = sys.stdin.readline
n, s = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
start = 0
end = 1
nowSum = arr[start]
ans = float('inf')
while True:
if end == n and nowSum < s:
break
if nowSum < s and end != n:
nowSum += arr[end]
end += 1
if nowSum >= s:
if ans > end - start:
ans = end - start
nowSum -= arr[start]
start += 1
if ans == float('inf'):
print(0)
else:
print(ans)