5557번 - 1학년(dp)

문제:

 

풀이:

숫자는 계산중에도 20을 넘길 수 없고 0이하로 떨어질 수도 없다.

바로 코드를 작성해보자.

import java.util.Scanner;

public class 일학년_5557번 {
    static int N;
    static long[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        dp = new long[N-1][21];

        int first = sc.nextInt();
        dp[0][first] = 1;

        for (int i = 1; i < N-1; i++) {
            int num = sc.nextInt();

            for (int j = 0; j <= 20; j++) {
                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];
                    }
                }
            }
        }

        int last = sc.nextInt();

        System.out.println(dp[N-2][last]);

    }
}

1. num1 +- num2 +- num3 .... = numN 이기 때문에 마지막에 들어오는 수는 배열에 저장할 필요가 없다.
   고로 dp배열의 크기는 dp[N-1][21]이다.
   자료형이 long인 이유는, 문제에서 나와있듯, 경우의 수의 최댓값은 int의 범위를 넘어가기 때문이다.
2. 먼저 첫번째 수를 입력받고 dp[0][first]에 1을 저장한다.
3. i = 1 ~ i = N -1 까지 반복문을 실행한다. -- i
   1. num에 다음 숫자를 입력받아 저장한다.
   2. 중간 계산의 결과는 0 ~ 20까지 무엇이든 가능하니, 반복문을 돌린다. -- j
      1. 만약 dp[i-1][j]가 0보다 크면, 즉 중간 계산의 결과이면이란 뜻이다.
         i가 1일때는 첫번째 입력(first)인 dp[0][first]에만 1이 저장되어 있다.
         1. j + num 이 20 미만일때, 즉 중간합산의 결과가 20 미만이면
            dp[i][j + num]에 dp[i-1][j]을 더해준다.
         2. 중간 뺄샘의 결과가 0 이상이면 dp[i][j - num]에 dp[i-1][j] 더해준다.
         3. 만일 중복이 되더라도 누적되서 dp[i-1][j]에 저장되기에 위 두 과정으로 중복을 피할 수 있다.
4. 마지막 숫자(last)를 입력받고, dp[N-2][last]를 출력해주면 된다.
   이 결과 num1 +- num2 +- num3 .... = numN 이 가능한 경우의 수가 출력되게 된다. 

 

시행착오:

중간연산의 범위가 크게 벗어나지 않으므로, dp를 사용하기 가장 좋은 경우 아니었나 싶다.

그래도 문제를 제대로 읽지 않아, dp 배열을 long 형이 아닌 int 형으로 설정해줬다.

문제를 제대로 읽고 실수를 줄여가도록 하자!