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

---

출력

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

 

# 정답 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            A[n] = Integer.parseInt(st.nextToken());
        }

        int i = 0;
        int j = 0;
        int sum = 0;
        int cnt = 0;

        while (i < N) {
            while (sum < M && j < N) {
                sum += A[j];
                j++;
            }

            if (sum == M) {
                cnt++;
            }

            sum -= A[i];
            i++;
        }

        System.out.println(cnt);
    }
}

 

배열 A에서 A[i]부터 A[j]까지의 합이 M과 같은 횟수를 찾는 코드이다.

A의 인덱스를 가리킬 포인터 i, j를 사용한다.

sum에는 현재 구간의 합을, cnt에는 합이 M과 같은 횟수를 저장한다.

 

i를 기준으로 j를 이동시키며 cnt를 찾기 위해, i가 N보다 작을 때까지 반복한다.

sum이 M보다 작고 j가 N보다 작으면, sum에 A[j]를 더하고 j를 1 증가한다.

만약 sum이 M과 같으면, cnt를 1 증가한다.

이제 i를 움직여야 하므로 sum에서 A[i]를 빼고 i를 1 증가한다.