백준 10844번 - 쉬운 계단 수 (Java 8)

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

10844번: 쉬운 계단 수

코드 :

dp

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static final int MOD = 1_000_000_000;
    static long[][] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        // 1부터 사용하기 위해 N+1
    	// 자릿수가 N개인 수에서, N번째 자릿수가 특정 수(1~9)일 때, 가능한 가짓수
        memo = new long[N+1][10]; 

        for (int i = 0; i <=9; i++) {
            memo[1][i] = 1L;
        }

        long result = 0L;

        for (int i = 1; i <= 9; i++) {
            result += dp(N,i);
        }
        System.out.println(result % MOD);
    }
    
    // 0이나 9일때는, 다음 자릿수에 1혹은 8밖에 오지 못한다.
    public static long dp(int digit, int val){
        if (memo[digit][val] == 0 && digit != 1) {
            if (val == 0) {
                memo[digit][val] = dp(digit - 1, 1);
            } else if (val == 9) {
                memo[digit][val] = dp(digit - 1, 8);
            } else {
                memo[digit][val] = dp(digit - 1, val - 1) + dp(digit - 1, val + 1);
            }
        }
        return memo[digit][val] % MOD;
    }
}

항상 감을 잡았다고 생각하는데, 다음날 다른 dp문제 풀면 새롭다. 이차원배열을 계속 사용할 생각을 못하는것 같다. 이차원 배열을 기억하고 계속 풀자.

참고 :

https://st-lab.tistory.com/134 블로그 포스팅 해주신 덕분에 살았다.