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

출력

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

예제 입력

4 2
1 1 1 1

예제 출력

3

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        long[] A = new long[N];

        // 배열에 저장
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        // 투 포인터
        int end = 0, cnt = 0, sum = 0;
        for (int start = 0; start < N; start++) {
            while (sum < M && end < N) {    // 합을 맞추는 end 찾기
                sum += A[end];
                end++;
            }
            if (sum == M) {     // 합이 맞았을 경우
                cnt++;
            }
            sum -= A[start];    // start 가 1 증가할 예정이므로 현재 start 가 가리키는 값을 제외
        }
        bw.write(cnt + "\n");

        br.close();
        bw.flush();
        bw.close();
    }
}

정리

알고리즘
1. 현재 부분의 합이 M보다 작다면, end가 가리키는 값을 sum에 더하고 end를 1 증가시킨다.
2. 현재 부분의 합이 M과 같다면, 카운트한다.
3. 현재 부분의 합이 M보다 크다면, start가 가리키는 값을 sum에서 빼고 start를 1 증가시킨다.

• 투 포인터의 시간복잡도는 O(N)이다.

참고링크
https://www.youtube.com/watch?v=rI8NRQsAS_s&t=438s