문제

BOJ 5557: 1학년 https://www.acmicpc.net/problem/5557

풀이

조건

• 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만든다.
• 만들 수 있는 올바른 등식의 수를 구한다.

풀이 순서

• DP를 사용한다.
• 2차원 배열을 사용한다.
  • 행은 숫자 연산을 하는 단계라고 생각한다.
  • 열은 각 행(단계)에서 나온 숫자라고 생각한다.
  • 2차원 배열 dp[3][11]을 예로 든다면
    • 입력받은 숫자 배열 3번째 연산 결과로 11이라는 수가 될 수 있는 연산의 경우의 수이다.
• 단계를 올려가며 다음 단계에서 나온 결과를 반영해간다.

코드

Java

import java.util.*;
import java.io.*;

public class Main {

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

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N]; // 입력 숫자 저장
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N - 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int total = Integer.parseInt(st.nextToken()); // 마지막 숫자

        long answer = 0; // 답
        
        // 메모이제이션 할 배열
        long[][] dp = new long[N + 1][21];
        dp[1][arr[1]] = 1; // 1 단계의 첫 번째 숫자를 만들 수 있는 경우의 수는 1
        
        // DP 시작
        for (int i = 1; i <= N - 2; i++) {
            // 0 ~ 20까지 각각 만들 수 있는 경우의 수 찾기
            for (int j = 0; j <= 20; j++) {
                // 만든 경우가 있을 때
                if (dp[i][j] != 0) {
                    // 현재 단계의 수에서 다음 단계 수를 더했을 때, 뺐을 때
                    int plus = j + arr[i + 1];
                    int minus = j - arr[i + 1];
                    // 범위 체크 + 경우의 수 반영
                    if (plus >= 0 && plus <= 20) {
                        dp[i + 1][plus] += dp[i][j];
                    }
                    if (minus >= 0 && minus <= 20) {
                        dp[i + 1][minus] += dp[i][j];
                    }
                }
            }
        }
        // 마지막 단계에서 찾는 수를 만들 수 있는 경우의 수
        answer = dp[N - 1][total];

        System.out.println(answer);
    }

}

정리

• 연산을 할 때 마다 나오는 수는 0 ~ 20인데 이를 이용해 DP를 할 수 있다는 점을 배웠다.