- 접근이 어려워 인터넷을 참고했다. 코드는 보지 않았다.
- 수의 길이가 i이면서 마지막 숫자가 j인 계단 수의 개수를 저장하는 것이 핵심이다.
- 점화식은 L[i][j] = L[i-1][j-1]+L[i-1][j+1] 이다.
1N = int(input())
2L = [[0]*12 for _ in range(100)]
3L[0] = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
4
5for i in range(1, N):
6 for j in range(1, 11):
7 L[i][j] = L[i-1][j-1]+L[i-1][j+1]
8
9print (sum(L[N-1])%1000000000)