[BOJ][C++] 1562번 계단 수

안녕하세요.오늘은 백준 1562번: 계단 수(링크)  문제를 풀어보려고 합니다. 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력10 예제 출력1 제한시간 제한: 2초메모리 제한: 128MB 풀이먼저 쉬운 계단 수를 풀고 오면 이해가 더 쉽다. 쉬운 계단 수에서 정의한 DP에 따르면 아래와 같은 점화식이 만들어진..