[백준] #2003 수들의 합2 - JAVA

❔ 문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

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

예제 입력1

4 2
1 1 1 1

예제 출력1

3

예제 입력2

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력2

3

🔍 문제 풀이

연속 부분 수열의 합을 구하는 문제이므로 투 포인터를 사용하여 해결할 수 있다.

1. left, right 두 개의 포인터를 사용하여 배열을 탐색.
2. sum 변수에 arr[left] ~ arr[right]까지의 합을 유지.
3. sum == m일 때 카운트하고, sum > m이면 left를 증가시켜 값 감소
4. right를 증가시키며 전체 배열을 한 번만 순회

예제 풀이
arr = [1, 2, 3, 4, 5], m = 5

#1 첫 번째 반복 (right = 0)

sum < m → 그대로 진행

#2 두 번째 반복 (right = 1)

sum < m → 그대로 진행

#3 세 번째 반복 (right = 2)

1. sum > m → sum 감소 후 left 이동
2. sum == m → cnt++

#4 네 번째 반복 (right = 3)

1. sum = 9 sum > m → sum 감소 후 left 이동
2. sum = 7 sum > m → sum 감소 후 left 이동
3. sum = 4 sum < m → 그대로 진행

#5 다섯 번째 반복 (right = 4)

1. sum > m → sum 감소 후 left 이동
2. sum == m → cnt++

따라서, cnt = 2

☑️ 최종 코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		
		int[] arr = new int[n];
		
		input = br.readLine().split(" ");
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(input[i]);
		}
		
		int cnt = 0 , sum = 0, left = 0, right = 0;
		while(right < n) {
			sum += arr[right];
			
			while(sum > m) {
				sum -= arr[left++];
			}
			if(sum == m) {
				cnt++;
			}
			right++;
		}
		System.out.println(cnt);
	}
}