[백준, Java] 5557번 : 1학년

🔗 문제 링크

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

😮 문제 해결 방법

처음부터 숫자를 더하거나 빼면서 그 값이 0이상 20이하가 되어야 한다.

완전탐색으로 문제를 풀기에는 경우의 수가 무수히 많기 때문에 DP를 이용한다.

 

dp 배열의 사이즈는 마지막 숫자를 제외한 숫자의 개수, 0 - 20까지 경우의 수를 저장하게 dp[N-1][21]로 지정한다.

마지막 숫자는 수식의 = 이되기 때문에 마지막 숫자는 배열에서 제외한다.

배열에는 매 인덱스 별 계산한 결과값의 경우의 수가 저장되어있다.

 

따라서, N-1 인덱스까지 숫자의 인덱스를 옮겨가면서 이전 인덱스까지 결과값 0에서 20까지의 경우의 수 중 1번 이상 결과가 나온 값을 더하거나 빼준다.

 

더하거나 빼준 값이 다시 0이상 20이하라면 현재 인덱스의 결과값에 이전 인덱스 경우의 수를 그대로 추가해준다.

마지막 숫자의 경우는 최종 결과값이기 때문에 dp 배열에서 최종 결과값을 가진 경우의 수를 반환한다.

 

✏️ 정리

1. dp배열 사이즈를 2차원 배열 형태로 [N-1][21]로 지정한다.
   • N-1 : 마지막 숫자는 최종 결과값이기 때문에 실제 연산에 들어가지 않는다.
   • 21 : 0에서 20이하의 수만 결과가 될 수 있다.
2. 숫자의 인덱스를 차례대로 돌면서 이전 인덱스까지 더하거나 뺀 결과 중에 0이상 20이하인 값이 있는 경우 (dp[index-1][0~20] > 0)
3. 해당 하는 결과와 현재 인덱스의 숫자를 더하거나 빼준다.
4. 더하거나 뺀 값이 0이상 20이하라면 이전 인덱스의 경우의 수를 현재 인덱스의 결과 값에 그대로 추가한다.
5. dp[N-2][numbers[n-1]]을 반환한다.
   • N-2 : dp 배열을 마지막 수를 제외하고 N-1크기로 지정했기 때문에 N-2가 해당 배열의 마지막 위치이다.
   • numbers[n-1] : 마지막 수는 결과값이 되므로 dp배열에서 마지막 수의 결과와 동일해주는 경우의 수만 반환한다.

🚩 Java 코드

package com.second.algorithm.baekjoon;

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

public class Main_5557_1학년 {
    private static int N;
    private static int[] numbers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        numbers = new int[N];
        for (int index = 0; index < N; index++) {
            numbers[index] = Integer.parseInt(st.nextToken());
        }

        long rst = getExpCount();
        System.out.println(rst);

        br.close();
    }

    private static long getExpCount() {
        long[][] dp = new long[N - 1][21];
        dp[0][numbers[0]] = 1;

        // N-1 index까지 확인하고 0부터 20이 되는 경우의 수를 더해준다.
        for (int index = 1; index < N - 1; index++) {
            for (int number = 0; number <= 20; number++) {
                // 이전 인덱스까지 더하거나 뺀 숫자 중에 0이상 20이하인 값이 있다면
                if (dp[index - 1][number] > 0) {
                    int plus = number + numbers[index];     // 이전 인덱스 더하거나 뺀 값 + 현재 위치의 숫자값
                    if (plus >= 0 && plus <= 20)
                        dp[index][plus] += dp[index - 1][number];   // 더한 값이 0 이상 20이하이면 가능한 경우의 수이므로 현재 인덱스에 경우의 수를 더해준다.

                    int minus = number - numbers[index];    // 이전 인덱스 더하거나 뺀 값 - 현재 위치의 숫자값
                    if (minus >= 0 && minus <= 20)
                        dp[index][minus] += dp[index - 1][number];  // 뺀 값이 0 이상 20이하이면 가능한 경우의 수이므로 현재 인덱스에 경우의 수를 더해준다.
                }
            }
        }

        // 마지막 숫자는 정답이 되야 하므로 제외 되기 때문에 (N-2)
        // 마지막 숫자의 경우의수를 구해야한다.
        return dp[N - 2][numbers[N - 1]];
    }
}