[백준] DP - 10844번, 쉬운 계단 수 (답지 봄)

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

문) 45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

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

 

입) 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출) 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

풀이

1. 테이블 정의

- 길이가 N인 계단수를 구하고, 1,000,000,000으로 나눈 나머지 출력

2. 점화식 - 이차원 배열!

• D[i][j] - i는 자릿수, j는 자릿값(0 < i < N, 0 <= j < 10)
• i=1, x... 1 2 3 4 5~ 한 자릿수는 경우의 수가 1밖에 없다.
• i=2, 2x... 자릿값이 0과 9인 경우와 아닌 경우로 나누어 봐야 함.
• (예외)11 / 98 : 자릿값이 0 또는 9인 경우 각각 1 또는 8 밖에 못 온다.
  • D[i][0] = D[j-1][1] 혹은 D[j][9]=D[i-1][8]
  • 1개씩 밖에 경우의 수가 없음.
• (보편)10 12 21 23 32 34~
  • D[i][j] = D[i-1][j-1] + D[i-1][j+1]
  • 그외는 2개씩 경우의 수가 있음.

3. 초기값 : D[1][i] = 1;

 

코드

Scanner + Bottom-Up(반복문) 방식

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(fn(N));
        sc.close();
    }
    static long fn(int n) {
        final long mod = 1000000000;

        long D[][] = new long[n+1][10];

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

 

다음엔 재귀를 활용한 Top-Down 방식과 Bottom-Up 방식에서도 bufferedReader를 써봐야겠다.