[boj] 백준 gold5 5557 1학년 (Java) - dp

[문제]

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

5557번: 1학년

 

[풀이]

dfs로 풀게 되면 O(2^n)의 시간복잡도를 갖게 된다.

dp를 통해 해결할 수 있는데 이전의 수에 현재 수를 +하거나 - 하는 2가지 경우가 존재한다. 또한 수가 0~20 사이에 존재해야 한다.

따라서 dp[i][num] 은 0~i 번까지의 수를 차례로 더하거나 빼서 num을 만들 수 있는 경우의 수로 두고 풀 수 있다.

 

[코드]

 

package dp;
import java.io.*;
import java.util.*;

public class boj_5557_1학년 {
    static int n;
    static int[] num;
    static long[][] dp;
    public static void main(String[] args) throws Exception{
        //상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오. 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        num = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        int last = num[n-1];
        dp = new long[n][21];

        dp[0][num[0]] = 1;
        for(int i=1; i<n-1; i++){
            for(int j=0; j<=20; j++){
                if(j+num[i] <= 20){
                    dp[i][j+num[i]] += dp[i-1][j];
                } 
                if(j-num[i]>=0){
                    dp[i][j-num[i]] += dp[i-1][j];
                }
            }

        }


        System.out.println(dp[n-2][last]);
    }


}