BOJ 10844. 쉬운 계단 수

BOJ 10844. 쉬운 계단 수

풀이

d[i][j] = 길이 i의 마지막숫자가 j인 수의 개수

길이 i의 마지막으로 오는수가 j일때 
마지막 수 j의 바로 전 수는 j+1 or j-1 일 수밖에 없다 (계단수는 인접한 모든 자릿수의 차이가 1이므로)
마지막 수 j로 끝났을 경우를 2차원 배열에 저장한다. 
j가 0일때는 j+1만 올 수 있고, j가 9 일때는 j-1만 올 수 있음을 주의한다.

점화식 d[i][j] = d[i-1][j-1] + d[i-1][j+1] , (1 < j <=9)

Bottom-Up

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] d = new long[n + 1][10];
        long mod = 1_000_000_000L;

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

        long result = 0;
        for (int i = 0; i <= 9; i++) result += d[n][i];
        System.out.println(result % mod);
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val d = Array(n + 1) { LongArray(10) }
    val mod = 1_000_000_000L

    for (i in 1..9) d[1][i] = 1
    for (i in 2..n) {
        for (j in 0..9) {
            d[i][j] = when (j) {
                0 -> (d[i - 1][j + 1]) % mod
                9 -> (d[i - 1][j - 1]) % mod
                else -> (d[i - 1][j - 1] + d[i - 1][j + 1]) % mod
            }
        }
    }
    (0..9).sumOf { d[n][it] }.let { it % mod }.let(::println)
}

Top-Down

import java.util.Scanner;

class Main {
    static long[][] d = new long[101][10];
    static long mod = 1_000_000_000L;

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

        for (int j = 1; j <= 9; j++) d[1][j] = 1;

        long result = 0;
        for (int j = 0; j <= 9; j++) {
            result += (go(n, j) % mod);
        }

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

    static long go(int i, int j) {
        if (d[i][j] > 0 || i == 1) return d[i][j];

        if (j == 0) {
            d[i][j] = go(i - 1, j + 1) % mod;
        } else if (j == 9) {
            d[i][j] = go(i - 1, j - 1) % mod;
        } else {
            d[i][j] = (go(i - 1, j - 1) + go(i - 1, j + 1)) % mod;
        }

        return d[i][j] % mod;
    }
}

val d = Array(101) { LongArray(10) }
const val mod = 1_000_000_000L

fun main() {
    val n = readLine()!!.toInt()
    for (i in 1..9) d[1][i] = 1

    ((0..9).sumOf { go(n, it) } % mod).let(::println)
}

fun go(i: Int, j: Int): Long {
    if (d[i][j] > 0 || i == 1) return d[i][j]

    d[i][j] = when (j) {
        0 -> go(i - 1, j + 1) % mod
        9 -> go(i - 1, j - 1) % mod
        else -> (go(i - 1, j + 1) + go(i - 1, j - 1)) % mod
    }

    return d[i][j] % mod
}

풀이소스

github.com/beomjo/algorithm-study/commit/7d1b464b3a06ce004cd071dc71af81c1ae751cd4#diff-1012b276a559252e4f3e8248e697ebbf45684020ae6683b2608c4a876d8b6fb8