Baekjoon | Q.10844 - 쉬운 계단 수

10844번: 쉬운 계단 수

동적 프로그래밍을 이용해서 계단 수의 개수를 찾는 문제이다.

package p10844;

import java.util.Scanner;

public class Main {
  static int[][] dp = new int[101][10];
  static final int mod = 1000000000;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.close();

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

    for (int i = 2; i <= n; i++) {
      for (int j = 0; j < 10; j++) {
        if(j == 0) {
          dp[i][0] = dp[i-1][1] % mod;
        }else if(j == 9) {
          dp[i][9] = dp[i-1][8] % mod;
        }else {
          dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
        }
      }
    }

    long sum = 0;
    for (int i = 0; i < 10; i++) {
      sum += dp[n][i];
    }

    System.out.println(sum % mod);
   
  }

}

 점화식을 찾기 어려워서 구글의 힘을 빌렸다...ㅎ 

 

dp[i][j]는 길이가 i이고 마지막 자리의 수가 j인 계단 수의 개수를 의미한다. 길이가 i이고 마지막 자리의 수가 j인 계단 수는 길이가 i-1이고 마지막 자리의 수가 j-1 또는 j+1인 계단 수의 끝에 j만 붙여주면 된다.

 

 예를 들자면 길이가 2인 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56... 가 있다. 길이가 3이고 마지막 자리의 수가 3인 계단 수는 길이가 2이고 끝 자리가 2 또는 4인 계단 수에 3만 붙여주면 된다. 따라서 123, 343, 323, 543 네 가지의 계단 수를 찾을 수 있다. 따라서 dp[i][j] = dp[i-1][j-1] + dp[i-1][j-1]의 점화식이 성립한다.

 

 그러나 j가 0이나 9일 경우에는 이 점화식이 성립하지 않으므로 따로 조건분기를 통해 처리해 주었다. j가 0일 경우 j-1 = -1이 되어 마지막 자리 수가 -1이 되버리고, j가 9일 경우 j+1 = 10이 되어 자리 수가 증가해버린다.

 

 따라서 최종 점화식은 다음과 같다.

j=0 일 때, dp[i][j] = dp[i-1][j+1]

0<j<9일 때, dp[i][j] = dp[i-1][j-1]+ dp[i-1][j+1]

j=9 일 때, dp[i][j] = dp[i-1][j-1]