연속부분수열 2

N개의 수로 이루어진 수열이 주어집니다.

이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N=5, M=5이고 수열이 다음과 같다면

1 3 1 2 3

합이 5이하가 되는 연속부분수열은 {1},{3},{1},{2},{3},{1,3},{3,1},{1,2},{2,3},{1,3,1}로 총 10가지 입니다.

 

입력설명

첫째 줄에 N,M이 주어진다.

수열의 원소값은 1,000을 넘지 않는 자연수이다.

 

출력설명

첫째 줄에 경우의 수를 출력한다.

 

입력예제 1

5 5

1 3 1 2 3

 

출력예제 1

10

 

answer부분을 --> rt-lt+1로 구현

해석해보자

예를 들어,

lt=0이고 rt=2인 경우 --> sum = 1+3+1 = 5를 나타낸다.

rt - lt + 1 = 2 - 0 + 1 = 3

여기서 말하는 3은

[1],[1,3],[1,3,1]을 나타낸다

왜이렇게 할까? --> 새롭게 추가된 숫자 + 새롭게 추가된 숫자를 포함한 숫자들의 조합

새롭게 추가된 숫자:1 / 숫자들의 조합: 1,3 / 1,3,1

이러한 방식으로 for문을 다 돌게되면, 10개의 경우가 생겨난다.