R00763
부분합
골드 IV레이팅
의견: 0
설명
길이가 \(N\)인 자연수 수열이 주어진다. 이 수열에서 연속된 부분 수열 중, 그 합이 \(S\) 이상이 되는 것 가운데 가장 짧은 것의 길이를 구하여라.
제약
\(1 \le N \le 100\,000\), \(1 \le S \le 10^9\), 각 원소는 \(10\,000\) 이하의 자연수.
입력 형식
첫째 줄에 \(N\)과 \(S\)가 주어진다. 둘째 줄에 수열의 원소 \(N\)개가 주어진다.
출력 형식
조건을 만족하는 가장 짧은 연속 부분 수열의 길이를 출력한다. 그런 부분 수열이 없으면 \(0\)을 출력한다.
예제 1
입력
10 15
5 1 3 5 10 7 4 9 2 8
출력
2
설명
5+10은 15 이상이고 길이 2. 더 짧은 부분 수열은 없다.
예제 2
입력
3 10
1 1 1
출력
0
설명
전체를 더해도 10이 안 되므로 0.
문제 시리즈
실버 V문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
부분합
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
부분합
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기