[JAVA] 백준 10844 DP

 

 

 

10844번: 쉬운 계단 수

문제

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

풀이

계단수는 이전 자리의 수에서 +1 혹은 -1한 수가 현재 자리에 올 수 있는 수를 말한다.

따라서 이전 자리 수에 따라서 그 다음에 오는 수에 영향을 끼친다. 따라서 이를 활용하여 DP배열을 만들고 문제를 풀었다.

먼저 첫 번째 자리에 오는 수를 생각해보자.

• 첫 번째 자리에 올 수 있는 수는 1 ~ 9까지 총 1개의 경우의 수밖에 없다.
• 즉, D[1][i] = 1이 된다. (D[1][0] = 0, 계단수에서 첫 번째 자리에 0이 올 수 없다.)

여기서 1자리가 존재할 때 계단 수는 D[1][i], i = 0 ~ 9의 합이 된다.

두 번째 자리에 오는 수를 생각해보자.

• D[2][0] = D[1][1]이 된다. 왜냐하면 2번째 자리에 0이 오는 경우의 수는 이전 자리 수에서 1이 오는 경우의 수밖에 없다.
• 동일한 이유로 D[2][9] = D[1][8]이 된다. (마찬가지로 9가 올 수 있는 경우의 수는 8밖에 없다. 10은 불가능)
• 나머지 1 ~ 8은 이전 자리의 +1 혹은 -1일 경우 가능하다.
  • 즉 다음과 같은 점화식이 가능하다.
  • D[2][i] = D[1][i-1] + D[1][i+1] (이전 자리에 +1 혹은 -1의 경우의 수)

2의 자릿수가 있을 때 계단 수의 종류 즉, 경우의 수는 D[2][i], i = 0 ~ 9를 모두 합한 값이 된다.

자 그럼 코드를 한번 살펴보자.

📌 1의 자릿수가 존재할 때로 계단수 DP배열을 초기화해준다.

        for(int i=1; i<10; i++){
            A[1][i] = 1;
        }

• 자릿수가 하나일 때 1 ~ 9까지의 경우의 수는 하나씩 존재한다.
• 즉, 자릿수가 하나라면 계단수의 경우의 수는 9가지이다.

📌 점화식을 통해 DP 배열을 만들어준다.

        for(int i=2; i<N; i++){
            // 현재 높이 i에서 0이 올 수 있는 경우의 수는 i-1의 높이에서 1이 오는 경우의 수
            A[i][0] = A[i-1][1];
            // 현재 높이 i에서 9가 올 수 있는 경우의 수는 i-1의 높이에서 8이 오는 경우의 수
            A[i][9] = A[i-1][8];
            for(int j=1; j<= 8; j++){
                // 현재 높이 i에서 j가 올 수 있는 경우의 수는 i-1에서 j+1 or j-1이 오는 경우의 수이다.
                A[i][j] = (A[i-1][j-1] + A[i-1][j+1] )%divide;
            }
        }

• 0과 9의 경우 -1과 +1을 할 경우 각각 -1과 10이 되기때문에 이런 수는 존재하지 않는다. 따라서 이전 값이 1이거나 8일 경우만 체크해준다.
• 1 ~ 8까지의 경우 위에서 설명한 점화식을 토대로 배열을 채워준다.

📌 경우의 수 구하기

        long sum = 0;
        for(int i=0; i<10; i++){
            // 현재 높이 N-1에서의 모든 경우의 수는 N-1에서 0 ~ 9가 올 수 있는 경우의 수를 모두 더한 값
            sum = (sum + A[N-1][i]) % divide;
        }
        System.out.println(sum);

• 자리수가 존재할 때 경우의 수는 0 ~ 9까지의 경우의 수를 모두 합한 값이된다.

📌 전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine())+1;
        int divide = 1_000_000_000;
        long[][] A = new long[N][10];

        // 높이가 1인 계단수는 1 (1 -> 1, 2 -> 1)
        for(int i=1; i<10; i++){
            A[1][i] = 1;
        }

        for(int i=2; i<N; i++){
            // 현재 높이 i에서 0이 올 수 있는 경우의 수는 i-1의 높이에서 1이 오는 경우의 수
            A[i][0] = A[i-1][1];
            // 현재 높이 i에서 9가 올 수 있는 경우의 수는 i-1의 높이에서 8이 오는 경우의 수
            A[i][9] = A[i-1][8];
            for(int j=1; j<= 8; j++){
                // 현재 높이 i에서 j가 올 수 있는 경우의 수는 i-1에서 j+1 or j-1이 오는 경우의 수이다.
                A[i][j] = (A[i-1][j-1] + A[i-1][j+1] )%divide;
            }
        }

        long sum = 0;
        for(int i=0; i<10; i++){
            // 현재 높이 N-1에서의 모든 경우의 수는 N-1에서 0 ~ 9가 올 수 있는 경우의 수를 모두 더한 값
            sum = (sum + A[N-1][i]) % divide;
        }
        System.out.println(sum);
    }
}

결과