11057번 오르막 수(DP)

#문제링크 : https://www.acmicpc.net/problem/11057

<전략>

1. 쉬운 계단 수와 같이 N번째 오르막 수에 올 수 있는 수는 0~9까지이다.

2. N번째 오르막수가 6이면 N-1번째 오르막 수는 0~6까지 올 수 있다. 즉, N이 M일때, N-1번째 수는 0~M까지이고, N-1번째 수가 될 수 있는 0~M까지의 모든 경우의 수를 더한 것이 N번째 오르막 수가 M일 때의 총 갯수이다.

3. N번째 오르막 수의 전체 갯수는 N번째 수가 0~9까지 일때의 경우를 모두 더한 값이 된다.

Code