쉬운 계단수

🧷 문제 https://www.acmicpc.net/problem/10844 정수 n이 주어졌을 때, 길이가 n인 모든 자리수의 차이가 1이 나는 계단수의 개수를 구하는 문제이다. 🛠 풀이 이 문제는 DP table을 1차원이 아닌 2차원으로 구성해야 해결할 수 있다. Step 1. 먼저 DP table을 d[자리수][끝자리 숫자] = 경우의 수로 구성한다. Step 2. 자리수 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 3 1 3 3 4 4 4 4 4 3 2 자리수가 1일때부터 보면, 자리수가 1일때는 당연하게도 경우의 수가 1이다. 자리수가 2일때부터는 맨 뒤에 0 또는 9가 오는 경우 특수하다. 첫번째로, 0으로 끝나는 경우 자..