[Java] 백준 풀기 2003 - 수들의 합 2

자바 백준 2003번

실버 4

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

 

 

 

 

문제 보기

분류: 브루트포스 알고리즘, 누적 합, 두 포인터

 

 

 

 

 

문제 풀기

수열의 첫번째 value를 시작으로 다음 value와 합하여 누적 합을 만들고, 그 누적 합을 다음 value와 합하여 다시 누적 합을 만드는 식을 반복하면서 주어진 수열의 마지막 value까지 누적 합하는 누적 합 array를 완성한다.

누적 합 array의 index가 큰 value와 index가 작은 value의 모든 차를 계산하여 M과 같은 경우 카운트를 늘린다. 이를 모든 경우에 대해 확인해 본다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();

        // 입력으로 주어진 수열 A를 저장할 배열
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        int count = findSubarraySumCount(A, M);
        
        System.out.println(count);
    }

    // i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수를 반환하는 함수
    private static int findSubarraySumCount(int[] A, int M) {
        int N = A.length;

        // 누적 합 배열 B 초기화
        int[] B = new int[N];
        B[0] = A[0];
        for (int i = 1; i < N; i++) {
            B[i] = B[i - 1] + A[i];
        }

        int count = 0; // 경우의 수를 저장할 변수

        // 모든 경우의 수를 탐색하면서 합이 M인 경우 카운트
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                int sum = B[j] - (i > 0 ? B[i - 1] : 0);
                if (sum == M) {
                    count++;
                }
            }
        }

        return count;
    }
    
}