[백준 - 21757][Gold 2][해설 X] - 나누기 (JAVA)

문제 링크

---

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

 

 

문제

---

 

 

입력

---

첫 번째 줄에 수열의 길이 N이 주어진다.

두 번째 줄에 N개의 정수 1,2,…,A1, A2, ... , AN이 공백 하나씩을 사이로 두고 주어진다.

 

출력

---

첫 번째 줄에 가능한 방법의 개수를 출력한다.

출력 값이 매우 클 수 있으므로 C, C++ 언어에서는 long long 형의 변수를, Java에서는 long 형의 변수를 사용해야 한다.

 

 

해결 코드

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] num = new long[N+1];
        long[] sum = new long[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1;i<=N;i++){
            num[i] = Long.parseLong(st.nextToken());
            sum[i] = sum[i-1] + num[i];
        }

        long[][] dp = new long[N+1][4];
        long count = 0;

        if(sum[N] %4 ==0){
            long target = sum[N]/4;

            dp[0][0] = 1;   //dp[1][1]이 가능한 경우을 위한 값

            for(int i=1;i<=N;i++){
                dp[i][0] = 1;   //dp[n][1]이 가능한 경우를 위한 값
                for(int j=1;j<=3;j++){
                    dp[i][j] = dp[i-1][j];  //이전까지 가능했던 경우의 수를 가져옴

                    if(sum[i] == target*j){ //현재까지의 누적합으로 부분 수열의 합이 가능하면
                        //이전 크기의 부분 수열이 가능한 만큼 추가로 되는 경우의 수이다.
                        dp[i][j] += dp[i-1][j-1];
                    }
                }
            }

            count = dp[N-1][3];
        }

        System.out.println(count);
    }
}

 

 

실행 결과

---

 

 

팁

---

• dp 점화식을 만들때 수평으로 움직이는 것이 아니라 수직으로도 움직일 수 있다는 것을 알자