[백준] 5557 1학년 - DP JAVA

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

5557번: 1학년

코드설명

DP 문제입니다.

 

처음에는 DFS로 간단하게 실행하여 만약 depth 가 N이라면 종료시키면서 마지막 결과값과 같은경우를 더해주면 될 것이라고 생각했습니다.

하지만, 그렇게할경우 각 선택마다 2배씩 계산횟수가 늘어나게 됩니다. 만약에 10번을 한다면 2^10 으로 1024번.문제에는 100개가 주어져있으니 2^100 의 개수가 나옵니다.

 

당연히 시간초과가 날 것입니다.

 

DP[N][21] 을 선언합니다. 여기서 N 부분은 자리수를 의미합니다. 2번째 차원인 21의 의미는 0부터 20까지의 숫자를 의미합니다.

즉, 예로들어보면, 3번째 자리수에서 결과값이 0부터 20까지이니 경우의 수를 메모리제이션 합니다.

그리고 문제에서 주어지듯 마지막 숫자는 결과값입니다.

그러므로, DP[N-2][arr[N-1]] 형식으로 출력하면 마지막 N-1 번째 자리수에서 결과값이 arr[N-1]인 경우의 수가 정답입니다.

 

코드

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

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[] arr;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	long[][] dp = new long[N][21]; //N번째 자리수에서 가능한 등식의 수 개수. 
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[0][arr[0]] = 1;
    	for(int i=1; i < N - 1; i++) {
    		for(int num=0; num<=20; num++) {
    			if(dp[i-1][num] > 0) {
    				int plusResult = num + arr[i];
    				int minusResult = num - arr[i];
    				if(plusResult >= 0 && plusResult <= 20) {
    					dp[i][plusResult] += dp[i-1][num];
    				}
    				if(minusResult >= 0 && minusResult <= 20) {
    					dp[i][minusResult] += dp[i-1][num];
    				}
    			}
    		}
    	}
    	
    	System.out.println(dp[N-2][arr[N - 1]]);
    
    	
	}
}