10844번 쉬운 계단 수(DP) - ☆

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

<전략>

1. 이친수와 달리 뒤에 추가될 수 있는 숫자가 0~9까지 총 10개이므로 d배열을 아예 d[n][10]과 같이 이중 배열로 선언.

2. d[n][0]과 d[n][9]는 계단 수가 되려면 각각 d[n-1][1], d[n-1][8]에만 의존한다.

3. 그외의 숫자들 d[n][m]은 d[n-1][m+1], d[n-1][m-1]의 값을 더한 것과 같은 경우의 수를 갖는다.

※주의사항

1. 정답 변수 ans는 d[n][0~9]까지의 합이므로 int최댓값보다 커질 수 있다. 따라서, long long으로 선언한다.

Code