[BOJ] 5557번 1학년 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int n;
    static int[] arr;
    static long[][] dp;
    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new long[n][21];  // dp[i][j] : i 번째 수까지 이용했을 때 j 번째 수를 만들 수 있는 경우의 수

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

    private static void process() {
        dp[0][arr[0]] = 1;
        // 1번 인덱스부터 확인, n-2 번째에 있는 수가 정답
        // 0 부터 20까지의 수 확인
        for (int i = 1; i < n - 1; i++) {
            for (int j = 0; j <= 20; j++) {
                if (dp[i - 1][j] != 0) {
                    // i 번째 수와 j의 합이 20 이하인 경우
                    if (j + arr[i] <= 20) {
                        dp[i][j + arr[i]] += dp[i - 1][j];
                    }
                    // i 번째 수와 j의 차가 0 이상인 경우
                    if (j - arr[i] >= 0) {
                        dp[i][j - arr[i]] += dp[i - 1][j];
                    }
                }
            }
        }
    }

    private static void print() {
        System.out.println(dp[n-2][arr[n-1]]);
    }

    public static void main(String[] args) throws IOException {
        init();
        process();
        print();
    }
}

📄 해설

접근

• DP 를 사용해서 푸는 문제. 보자마자 1차적으로 DFS 로 푸는 방법을 생각하고 접근하였음
• 그러나 DFS 를 통한 풀이법은, 시간초과가 발생하므로 DP 를 사용해서 풀어야한다.
• 또한, 숫자를 저장할 배열 arr 은 int 타입으로 선언을 해도 지장이 없으나, DP 테이블로 사용될 dp 의 경우 long 타입으로 선언을 해야함. ($2^{63}-1$ 이 최댓값이므로, long 타입 사용)

과정

위와 같이 DP 테이블을 직접 작성해서 풀어보면 점화식이 유도됨. 본 이미지는 다른 블로그를 참조하였음
[참조 블로그]

dp 테이블은 2차원 배열을 사용하며, 테이블의 의미는 다음과 같다.

• 숫자 배열 arr 에서 i 번째 수까지 이용했을 때 j 번째 수를 만들 수 있는 경우의 수

점화식은 i 번째 수와 j 번째 수의 합과 차일 경우 달라지며, 아래와 같다

• 덧셈기호를 사용한 경우
  dp [i][prev+arr [i]] += dp [i-1][prev]

• 뺄셈기호를 사용한 경우
  dp [i][prev-arr [i]] +=dp [i-1][prev]

두 경우 모두 결과가 0 이상인지, 20 이하인지 확인하며 진행해야함
위의 테이블을 보면 알 수 있듯이 정답 값은 dp[n-2][[arr[n-1]] 에 저장되어있음. (n-1 번째 수까지 사용 했을 때, n 번째 수를 만들 수 있는 경우의 수)