Java
첫 번째 줄에는 주어지는 숫자 개수 N과 더해서 만들어야 하는 숫자 M이 주어진다.
두번째 줄에는 N개의 숫자 배열이 주어진다.
연속한 일련의 숫자를 더하였을 때 M이 나오는 경우의 수를 출력한다.
상당히 간단한 설명의 문제이기에 아래 그림으로 일축한다.
완전 탐색은 시간 소요가 크기 때문에 투 포인터를 사용해준다.
투포인터 작동 원리를 그림으로 표현하면 다음과 같다.
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
//Input
int N = Integer.parseInt(str.split(" ")[0]);
long M = Integer.parseInt(str.split(" ")[1]);
str = br.readLine(); // 다음 줄을 읽어준다.
String[] array = str.split(" "); //배열을 담아준다.
int start = 0; // start 포인터
int end = 0; // end 포인터
int[] arr = new int[N];
for(int i = 0; i<N;i++) {
arr[i] = Integer.parseInt(array[i]);
}
long sum = 0; // 합
int result = 0; // 총 경우의 수
while(start < N) { //start가 끝까지 훑을 때까지
if(sum >= M || end == N) { //만약 sum이 M보다 크거나 같으면
sum -= arr[start]; //start 포인트가 앞으로 옮겨지므로 현재 point의 값은 수열에서 제외 --> sum에서 빼준다.
start++;// start point를 앞으로 옮겨준다.
}
//만약 sum이 M보다 작다면
else {
sum += arr[end]; // end point를 더해준 후
end++;// end point를 앞으로 옮겨준다.
}
//만약 합이 목표 합과 같다면
if (sum == M){
result++; // 결과를 하나 더해준다.
}
}
System.out.print(result);
}
}