문제 설명
외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,100] 범위 안에 들어가는 자연수 수열로 주어진다.
이 전파가 과연 단순한 노이즈인지 아니면 의미 있는 패턴을 가지고 있는지 파악하고 싶다.
전파의 부분 수열 중에 합이 K인 것이 유독 많다는 사실을 눈치채고 합이 K인 부분 수열이 몇 개나 있는지 계산하고 싶다.
예를 들어 주어진 자연수의 수열이 다음과 같다고 하자.
K의 값이 77이라면 [77], [17,60], [47,30]과 같이 3개의 구간에서 구간의 합이 77이 된다.
이 전파가 과연 단순한 노이즈인지 아니면 의미 있는 패턴을 가지고 있는지 파악하고 싶다.
전파의 부분 수열 중에 합이 K인 것이 유독 많다는 사실을 눈치채고 합이 K인 부분 수열이 몇 개나 있는지 계산하고 싶다.
예를 들어 주어진 자연수의 수열이 다음과 같다고 하자.
20, 88, 48, 77, 32, 50, 2, 17, 60, 50, 44, 47, 20, 88, 73, 43, 45, 47, 30, 39
K의 값이 77이라면 [77], [17,60], [47,30]과 같이 3개의 구간에서 구간의 합이 77이 된다.
입력 설명
1번째 줄에 전파 수열의 원소 개수\((N)\)와 합\((K)\)가 주어진다.\((1 \le N \le 1,000,000, 1 \le K \le 1,000,000)\)
2번째 줄에 \(N\)개의 자연수 수열이 입력된다. 수열의 각 값은 100이하이다.
2번째 줄에 \(N\)개의 자연수 수열이 입력된다. 수열의 각 값은 100이하이다.
출력 설명
합이 (K)인 부분 수열의 개수가 출력된다.
입력 예시 Copy
20 77
20 88 48 77 32 50 2 17 60 50 44 47 20 88 73 43 45 47 30 39
출력 예시 Copy
3