0%

[백준/10844] 쉬운 계단 수

작성일 Edited on In Disqus:

Baekjoon Online Judge - 10844

Review

  • 쉽게 말하자면 끝수-1을 변수 j라고 했을 때, 계단수는 j+1, j-1이 됨.
  • 예를 들어 자릿수가 3이고 27의 계단수를 구한다고 했을 때, 계단수는 27(7-1), 27(7+1)로 각 276, 278이 된다.
  • 구하려는 끝수를 변수 i이라고 한다면, 점화식은 다음과 같다.
  • dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
  • 시작이 0일 경우, 끝이 9일 경우의 처리를 반드시 해주어야 한다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;

public class Main {

  public static void main(String args[]) throws IOException{
    int[][] dp = new int[101][10];
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int MOD = 1000000000;
    long sum = 0;

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

    for(int i = 2; i <= n; i++) {
      for(int j = 0; j <= 9; 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;
        }
      }
    }


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

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