백준 5557번 1학년 (JAVA)

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

5557번: 1학년

 

저는 DP를 통해 문제를 해결하였습니다.

저는 DP[인덱스][현재까지의 합] = 이때까지의 가짓수 로 저장하였습니다.

결과가 2^(63)-1 이기 때문에 long 타입으로 저장하였습니다.

 

package BOJ.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_5557 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int[] input = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i++){
            input[i] = stoi.apply(st.nextToken());
        }
        long[][] dp = new long[n][LIMIT+1];
        for(int i = 0 ; i < n ; i++){
            Arrays.fill(dp[i],NOT_VALID);
        }
        long result = dfs(1,input[0],input,n,dp);
        System.out.println(result);
    }

    private static final long NOT_VALID = -1;
    private static final int LIMIT = 20;
    private static long dfs(int depth, int sum, int[] input, int n, long[][] dp) {
        if(depth == n-1){
            if(sum == input[n-1]){
                return 1;
            }else{
                return 0;
            }
        }
        if(dp[depth][sum] != NOT_VALID){
            return dp[depth][sum];
        }
        long result = 0;
        if(sum + input[depth] >= 0 && sum + input[depth] <= LIMIT){
            result += dfs(depth+1,sum + input[depth],input,n,dp);
        }
        if(sum - input[depth] >= 0 && sum - input[depth] <= LIMIT){
            result += dfs(depth+1,sum - input[depth],input,n,dp);
        }
        dp[depth][sum] = result;
        return result;
    }
}