•시간제한: 1.000 S •메모리제한: 256 MB •제출: 3 •통과: 1 •만든사람: suakii

코드제출 채점기록 통계 문제 풀기 묻고답하기

3209 : 계단 수 2

시간 1.000s · 메모리 256MB · 제출 3 · 정답 1

코드제출 문제 풀기

채점기록 통계 묻고답하기

이전 문제 다음 문제

인접한 모든 자릿수의 차이가 $1$인 수를 계단 수라고 합니다. 예를 들어 $45656$은 계단 수입니다.

$N$자리 계단 수의 개수를 $1{,}000{,}000{,}000$으로 나눈 나머지를 구하세요.

앞에 $0$이 오는 수는 제외합니다.

[제약 조건]
• $1 \le N \le 1000$
• $N$은 정수

첫째 줄에 정수 $N$이 주어집니다.

$N$자리 계단 수의 개수를 $1{,}000{,}000{,}000$으로 나눈 나머지를 출력하세요.

10자리 계단 수의 개수는 2,986개입니다.

동적계획법/메모이제이션