[BOJ/JAVA] 2003. 수들의 합 2

AmeriKano·2023년 4월 3일

문제 링크

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

출력

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

입력 예시

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

출력 예시

접근 방법

단순하게 생각하면, 모든 부분합의 경우의 수를 생각하여 풀 수 있을것이다. 다만 그렇게 해결하면 시간 복잡도가 $O(N^2)$ 이 되는데, 이 문제를 $O(N)$ 의 복잡도로 해결할 수 있는 방법이 있다. 바로 투 포인터 알고리즘이다.
투 포인터 알고리즘이란, 시작점과 끝점(문제에서 각각 i와 j)을 정해놓고, 원하는 합보다 작은 경우 끝점을, 큰 경우 시작점을 오른쪽으로 한 칸씩 옮기면서 배열의 전체를 순회하는 알고리즘이다. 이 과정을 거치면서 부분합이 M과 같아지면 한 가지의 경우가 성립하는 것이니 count를 더해주고, 이를 반복하다가 끝점이 배열의 맨 끝을 넘어가 버리면 더이상 찾을 수 없으므로 순회를 종료한다.

소스 코드

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());
        int m = Integer.parseInt(st.nextToken());
        int[] array = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        int i=0, j=0, sum=0, count=0;

        while (true) {
            if (sum > m) sum -= array[i++];
            else if (j == n) break;
            else sum += array[j++];

            if(sum == m) count++;
        }

        bw.write(count+"\n");
        bw.flush();
    }
}