n=int(input())answer=[[0,1,1,1,1,1,1,1,1,1]]for i in range(1,n): l=[]
for j in range(10): if j==0:
l.append(answer[i-1][j+1]) elif j==9:
l.append(answer[i-1][j-1]) else:
l.append(answer[i-1][j-1]+answer[i-1][j+1]) answer.append(l)
print(sum(answer[-1])%1000000000)https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net
하나씩 손으로
써보다보면 규칙이 보인다.
arr[i][j]는 [i]자리의 끝이[j]인 계단수의 개수이다.
처음엔 0을 제외한 모든수가 계단수이므로
[0.1.1.1.1.1.1.1.1.1]이다.
두번째에는[1,1,2,2,2,2,2,2,1]이다.
이를 반복하면
arr[i][j]=arr[i-1][j-1] + arr[i-1][j+1]이라는 식을 찾을 수 있다.
파이썬에서 indexerror방지를 위해서 j가 0 또는 9일때만 예외를 설정하여
0일때는 그 전의 1의값만, 9일때는 그 전의 8의값만 더해주면
문제를 풀 수 있다.