부분합
면접 대비시간 제한0.5초메모리 제한128 MB
합이 S 이상인 연속 부분열 중 가장 짧은 길이를 구하고, 없으면 0을 출력합니다.
문제
길이가 N인 수열이 주어진다. 모든 원소는 10,000 이하의 자연수이다.
이 수열에서 연속한 하나 이상의 원소를 골라 만든 부분합 중 합이 S 이상인 것만 생각한다. 그중 길이가 가장 짧은 부분수열의 길이를 구하라.
입력
첫째 줄에 정수 N과 S가 공백으로 구분되어 주어진다. (10 <= N < 100,000, 0 < S <= 100,000,000)
둘째 줄에 수열의 N개 원소가 공백으로 구분되어 주어진다. 각 원소는 10,000 이하의 자연수이다.
출력
합이 S 이상인 연속 부분수열 중 최소 길이를 출력한다. 그런 부분수열이 없으면 0을 출력한다.