[BaekJoon] 21757 나누기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int seriesCount;
    static int[] series;
    static int[] prefixSum;

    static void input() {
        Reader scanner = new Reader();

        seriesCount = scanner.nextInt();
        series = new int[seriesCount + 1];
        prefixSum = new int[seriesCount + 1];

        for (int idx = 1; idx <= seriesCount; idx++) {
            series[idx] = scanner.nextInt();
            prefixSum[idx] = prefixSum[idx - 1] + series[idx];
        }
    }

    /*
     * 총 4개의 연속된 부분으로 나눠야하기 때문에 누적합을 이용하여 각 부분의 합을 알 수 있다
     *  - 누적합에서 각 부분이 가지는 합은 수열의 전체 합을 4로 나눈 값을 공차로 하고, 수열의 전체 합을 4번째 항으로 하는 등차수열을 이룬다
     *  - 즉, 만약 수열의 전체 합이 12라고 한다면, 네 개의 부분은 누적합에서 3, 6, 9, 12라는 값으로 이루어진다
     *  - 그렇기 때문에 수열의 전체 합이 4로 나누어떨어지지 않으면 4개의 부분으로 나눌 수 없다!
     * 4개의 부분으로 나눌 수 있는 경우에는 DP를 이용하여 가능한 방법의 개수를 구한다
     *  - dp[x][y] = x번째까지 y번으로 나누는 경우의 수
     *  - y번으로 나누는 경우라면 공차 * y가 해당 위치의 누적합과 같을 때를 의미한다
     *  - 이전 경우의 수들을 계속해서 누적해나가야하기 때문에 dp[x][y] 값을 dp[x - 1][y]값으로 초기화한다
     *  - 그리고 만약 공차 * y와 현재 위치의 누적합이 같다면 해당 부분까지 하나의 부분으로 나눌 수 있다는 의미가 되므로
     *    dp[x][y]에 dp[x - 1][y - 1]값을 추가한다
     *      - 현재 위치를 y번으로 나누는 경우의 수는 이전까지 y - 1번으로 나누는 경우의 수가 되기 때문!
     */
    static void solution() {
        if (prefixSum[seriesCount] % 4 != 0) {
            System.out.println(0);
            return;
        }

        int diff = prefixSum[seriesCount] / 4;
        long[][] dp = new long[seriesCount + 1][5];
        dp[0][0] = 1;
        for (int idx = 1; idx <= seriesCount; idx++) {
            dp[idx][0] = 1;
            for (int idx2 = 1; idx2 < 4; idx2++) {
                dp[idx][idx2] = dp[idx - 1][idx2];
                if (diff * idx2 == prefixSum[idx]) {
                    dp[idx][idx2] += dp[idx - 1][idx2 - 1];
                }
            }
        }

        System.out.println(dp[seriesCount - 1][3]);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}