📖 [백준알고리즘 풀이] Q.2003 수들의 합 2 풀이 누적합 방식 - java

📖 문제

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

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의

합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

🔍 접근법

Q.2003 수들의 합 2 문제입니다.

i번째 수부터 j번째 수까지의 연속 된 합이 M이 되는 경우의 수를 구하는 문제입니다.

여기서 i번째 수부터 j번째 수까지 연속 된 합을 구하는 문제이므로

누적합을 이용해서 쉽게 풀이가 가능합니다.

j번째까지의 누적합을 모두 구하고나면

쉽게 i번째 수 부터 j번째 수까지의 합을 구할 수 있습니다.

i번째->j번째 수 까지의 연속 된 합 = j번째까지의 누적합 - i번째까지의 누적합 + i번째의 수

이므로 이중 for문을 이용해

각각의 i번째 수부터 j번째 수 까지의 합이 m이 되는 경우의 수를 구할 수 있습니다.

💻 코드

package problem.sum;

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

public class Main_2003 {
    static int n,m;
    static int numbers[];
    static int d[];
    static int count = 0;


    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(count);
    }

    public static void solve(){
        d[0] = numbers[0];
        for(int i=1; i<n; i++) {
            d[i] = d[i-1]+numbers[i];
        }
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(d[j]-d[i]+numbers[i] == m){
                    count++;
                }
            }
        }
    }


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp[] = br.readLine().split( " ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        numbers = new int[n];
        d = new int[n];
        temp = br.readLine().split(" ");
        for(int i=0; i<n; i++){
            numbers[i] = Integer.parseInt(temp[i]);
        }
    }

}

Written on March 9, 2021