연속 부분합을 모두 살피기 위해서는 $O(N^2)$ 시간이 걸립니다. 좀 더 빠른 풀이가 필요합니다.
수열의 모든 수가 자연수이기 때문에, 연속된 수의 길이가 늘어나면 부분합은 반드시 증가합니다.
오른쪽 끝이 $1, 2, \cdots, i$번째 수인 부분합을 모두 살펴봤다고 하고, $j$번째 수부터 $i$번째 수까지의 합이 $S$ 이상인 최대의 $j$를 찾았다고 합시다.
그러면 $j$번째 수부터 $i + 1$번째 수까지의 합은 반드시 $S$ 이상이므로, 오른쪽 끝이 $i + 1$번째 수인 부분합을 살펴볼 때는 왼쪽 끝을 $j + 1$부터 하여 살펴보면 충분합니다.
이는 덱을 이용하여 쉽게 구현할 수 있고, 각 수가 최대 한 번씩만 덱에 추가되고 삭제되므로 시간 복잡도는 $O(N)$입니다.
코드
use std::{
collections::VecDeque,
io::{stdin, Read},
};
fn main() {
let mut input = String::new();
stdin().read_to_string(&mut input).unwrap();
let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
let n = input.next().unwrap();
let s = input.next().unwrap();
let mut min_len = usize::MAX;
let mut deque = VecDeque::with_capacity(n);
let mut sum = 0;
for num in input {
sum += num;
deque.push_back(num);
while sum >= s && !deque.is_empty() {
min_len = min_len.min(deque.len());
sum -= deque.pop_front().unwrap();
}
}
if min_len == usize::MAX {
println!("0");
} else {
println!("{min_len}");
}
}