[BOJ 10844] 쉬운 계단 수 (Java, DP)

 

---

문제 링크

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

문제 풀이

 

- 시간 복잡도 : O(N * 10) = O(N)

- MOD를 나누지 않으면 터지는 이유 확인 필요

 

DP[i][j] = i 는 자리수 이고, j는 j로 끝나는 수를 뜻함

i\j	0	1	2	3	4	5	6	7	8	9
1	0	1	2	3	4	5	6	7	8	9
2	10	21	12, 32	23, 43	34, 54	45, 65	56, 76	67, 87	78, 98	89

 

---

제출 코드

 

1) Bottom-Up 방식

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

public class Main {
    
    static int N;

    static int[][] DP;

    static int MOD = 1000000000;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        DP = new int[N + 1][10];
        for(int i = 1; i <=9; i++) {
            DP[1][i] = 1;
        }
    }

    static void pro() {
        for(int i = 2; i <= N; i++) {
            for(int j = 0; j <= 9; j++) {
                DP[i][j] = 0;
                if(j > 0) DP[i][j] += DP[i - 1][j - 1];
                if(j < 9) DP[i][j] += DP[i - 1][j + 1];

                DP[i][j] %= MOD;
            }
        }

        int result = 0;
        for(int v : DP[N]) {
            result += v;
            result %= MOD;
        }
        System.out.println(result);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

2) Top-Down

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

public class Main {
    
    static int N;

    static Long[][] _DP;

    static int MOD = 1000000000;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        _DP = new Long[N + 1][10];
        for(int i = 1; i <=9; i++) {
            _DP[1][i] = 1L;
        }

        _DP[1][0] = 0L;
    }

    static void proByTopDown() {
        long result = 0L;
        for(int i = 0; i <= 9; i++) {
            result += topDown(N, i);
            result %= MOD;
        }

        System.out.println(result);
    }

    static long topDown(int depth, int idx) {
        if(depth == 1){
            return _DP[depth][idx];
        }

        if(_DP[depth][idx] == null) {
            if (idx == 0) {
                _DP[depth][idx] = topDown(depth - 1, idx + 1);
            } else if (idx == 9) {
                _DP[depth][idx] = topDown(depth - 1, idx - 1);
            } else {
                _DP[depth][idx] = topDown(depth - 1, idx - 1) + topDown(depth - 1, idx + 1);
            }
        }

        return _DP[depth][idx] %= MOD;
    }

    public static void main(String[] args) throws Exception {
        input();
        proByTopDown();
    }
}