[백준 2003번][Java][투 포인터] 수들의 합 2

2003번: 수들의 합 2 (acmicpc.net)

2003번: 수들의 합 2

문제

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을 넘지 않는 자연수이다.

출력

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

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class No2003_SumOfNumbers2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 수열 값 넣을 배열 생성
        int[] A = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // 포인터 p1, p2 생성
        int p1 = 1;
        int p2 = 1;
        int sum = 0;
        int cnt = 0;

        while (true) {
            if (sum > M) { // sum 이 M보다 클때 A[p1] 빼고, p1을 오른쪽으로 옮긴다.
                sum -= A[p1++];
            } else if (p2 == A.length) { // p2 가 A의 끝에 도달하면 while문 탈출
                break;
            } else { // 나머지 경우에는 A[p2]값을 더해주고 p2를 오른쪽으로 옮긴다.
                sum += A[p2++];
            }

            if (sum == M) { // sum 이 M과 같은 경우 경우의 수 +1
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}