[백준] 5557번 1학년

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   수열이 주어지고 수열 사이에 '+', '-'를 넣어 만들어진 식이 수열의 마지막 숫자와 등식을 만족하는 경우의 수를 구하는 문제이다. 예를 들면, "8 3 2 4 8 7 2 4 0 8 8"이 주어진 경우 "8+3-2-4+8-7-2-4-0+8=8"와 같이 만들 수 있다.

   첫째 줄에는 숫자의 개수 N이 주어지고, 둘째 줄에는 0이상 9이하의 정수 N개가 공백으로 구분해 주어진다. 제약 사항은 다음과 같다.

 

• 식은 왼쪽부터 계산하며, 계산 도중 나오는 수는 모두 0이상 20이하이어야 한다.
• 3 ≤ N ≤ 100
• 0 ≤ 출력 ≤ 26^3 - 1

---

접근 방식

   DP의 개념을 이용해 문제를 해결하였다. 문제의 핵심은 수열의 각 수들이 들어올 때 만들 수 있는 수와 그 수의 개수이다. 이때 만들 수 있는 수의 유효 범위는 0 ~ 20이라는 점을 주의해야 한다. 따라서 저장할 2차원 배열은 dp[수열의 K번째 수][만들 수 있는 수의 범위(0 ~ 20)]의 형태로 나타낼 수 있다. 이제 간단한 예제를 통해 과정을 이해해보자.

 

 

   수열은 "4 3 5 1 0 2"로 들어오고 범위는 임의로 줄여 0 ~ 6인 경우만 가능하다. 우선 1행 4번 인덱스값을 1로 초기화한다. 수열의 첫번째 값은 따로 ± 연산은 필요없기 때문에 이 과정은 단순히 4라는 값이 1개 존재한다는 의미이다.

   이제 두번째 행으로 넘어가자. 두번째 행은 수열의 두번째 숫자 3이 들어와 이전 값들과의 연산을 통해 만들어질 수 있는 수들을 의미한다. 첫번째 행에서 유효한 값은 인덱스 4이므로 '4 + 3', '4 - 3' 두 연산이 가능하다. 하지만 '4 + 3'의 경우 유효 범위(0 ~ 6)을 벗어나기 때문에 고려 대상이 아니다. 따라서 2행은 1인덱스만 유효하며 값은 이전 값의 경우의 수를 더해주게 된다.

 

 

   3번째의 경우도 크게 다르지 않기 때문에 설명은 생략한다.

 

 

   4번째 행의 경우 두 연산 모두 유효한 결과를 가진다.

 

 

   5번째 행의 경우 0에 의한 연산이기 때문에 이전 행과 동일한 결과를 갖는다.

 

 

   수열의 마지막 수는 계산 결과이기 때문에 최종적으로 5행의 인덱스 2번의 결과를 출력한다. 해당 과정을 통해 점화식은 다음과 같은 형태로 생각할 수 있다.

 

• dp[현재 행][이전 유효 인덱스 ± 수열의 k번째 수] = dp[이전 행][이전 유효 인덱스]

---

코드

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

public class 백준5557번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        token = new StringTokenizer(br.readLine());
        //경우의 수가 int 범위를 초과할 수 있기 때문에 long으로 선언
        //long[수열의 개수 - 1][만들어질 수 있는 수의 범위]
        long[][] dp = new long[N - 1][21];

        //수열의 첫번째 값 셋팅
        dp[0][Integer.parseInt(token.nextToken())] = 1;
        for (int i = 1; i < N - 1; i++) {
            //현재 수열의 값
            int num = Integer.parseInt(token.nextToken());
            for (int j = 0; j <= 20; j++) {
                //이전에 만들어진 숫자에 현재 수열의 값을 +- 연산
                //연산 과정에서 범위(0 ~ 20)를 벗어나는지 확인
                if (dp[i - 1][j] != 0) {
                    if (j + num <= 20)
                        dp[i][j + num] += dp[i - 1][j];
                    if (j - num >= 0)
                        dp[i][j - num] += dp[i - 1][j];
                }
            }
        }
        
        System.out.println(dp[N - 2][Integer.parseInt(token.nextToken())]);
    }
}