[백준] BOJ_5557 - 1학년

👀 문제 분석

1. 제약 조건 파악

• N의 크기:
• 중간 계산 값:
• 최종 결과: 이하 (Java의 long 타입 범위)

처음 문제를 접했을 때, 단순히 각 숫자 사이에 + 또는 -를 넣는 모든 경우를 구하는 완전 탐색(DFS)을 떠올릴 수 있다. 하지만 이 최대 100이므로, 가능한 경우의 수는 $2^{N-2}$가 되어 약 이라는 어마어마한 수치가 나온다. 즉, 일반적인 재귀나 브루트포스로는 절대 제한 시간 내에 통과할 수 없다.

2. 핵심 키워드

• "경우의 수": 특정 상태를 중복해서 계산해야 할 확률이 높다.
• "0 이상 20 이하": 중간 계산 결과의 범위가 굉장히 제한적이다. 이는 DP(Dynamic Programming)의 메모이제이션을 활용하기 위한 강력한 힌트가 된다.

---

💡 알고리즘 설계

1. 사용 알고리즘 & 자료구조

• 알고리즘: 동적 계획법 (Dynamic Programming)
• 자료구조: long[][] dp (경우의 수가 매우 크므로 long 필용)

2. 시간 복잡도

• : 숫자의 개수()만큼 반복하며, 각 단계에서 가능한 결과값()을 확인한다.
• 약 번의 연산으로 제한 시간 1초 내에 매우 여유롭게 통과 가능하다.

3. 핵심 로직 (DP 테이블 정의)

dp[i][j] = i번째 숫자까지 연산했을 때, 결과값이 j가 되는 경우의 수

1. 초기화: 첫 번째 숫자는 무조건 양수이므로 dp[1][A[1]] = 1로 시작한다.
2. 점화식: dp[i-1][j]에 값이 존재한다면 (즉, 이전 단계에서 j를 만들 수 있었다면):

• j + A[i]가 20 이하일 때: dp[i][j + A[i]] += dp[i-1][j]
• j - A[i]가 0 이상일 때: dp[i][j - A[i]] += dp[i-1][j]

3. 결과: N-1번째 숫자까지 연산한 결과가 마지막 숫자 A[N]과 같은 경우인 dp[N-1][A[N]]을 출력한다.

---

💻 코드 구현

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int[] A;
    static long[][] dp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        A = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // dp[i][j]: i번째 숫자까지 사용해서 j를 만드는 경우의 수
        // j의 범위가 0~20이므로 크기를 21로 설정
        dp = new long[N + 1][21];
        
        // 첫 번째 숫자의 경우의 수 초기화
        dp[1][A[1]] = 1;

        // 2번째 숫자부터 N-1번째 숫자까지 연산 진행
        for (int i = 2; i < N; i++) {
            for (int j = 0; j <= 20; j++) {
                // 이전 단계에서 j를 만들 수 있는 경우가 없다면 스킵
                if (dp[i - 1][j] == 0) continue;

                // 1. 더하기 연산
                if (j + A[i] <= 20) {
                    dp[i][j + A[i]] += dp[i - 1][j];
                }
                
                // 2. 빼기 연산
                if (j - A[i] >= 0) {
                    dp[i][j - A[i]] += dp[i - 1][j];
                }
            }
        }

        // N-1번째 연산 결과가 마지막 숫자(A[N])가 되는 경우의 수 출력
        System.out.println(dp[N - 1][A[N]]);
    }
}

---

✨ 회고

핵심 포인트

이번 문제의 핵심은 중간 연산 결과의 제한()을 보고 상태 공간을 압축할 수 있느냐였다. long 타입을 사용해야 한다는 점도 놓치지 말아야 할 포인트다. (경우의 수가 2의 63승 근처까지 갈 수 있기 때문)

시행착오 (삽질)

처음에는 단순히 DFS(완전 탐색)로 접근했다. "숫자가 100개니까 금방 끝나겠지?"라는 안일한 생각이었으나, 재귀 트리가 깊어질수록 지수적으로 늘어나는 연산 횟수를 감당하지 못하고 시간 초과가 발생했다.

다시 문제를 보니 "중간 계산 결과는 0 이상 20 이하"라는 매우 구체적인 조건이 있었다. "아, 결과값이 한정되어 있으니 동일한 결과가 나오는 수많은 경로를 하나로 합칠 수 있겠구나!"라는 깨달음을 얻었고, 곧바로 DP로 선회하여 해결할 수 있었다.

Lesson Learned: 제약 조건에 특정 숫자의 범위가 작게 주어지는 경우, 해당 범위를 DP의 인덱스로 활용할 수 있는지 반드시 체크하자!