[백준 10844]

1. 코드 (실패)

n= int(input())

dp = [[0]*9 for j in range(n+1)]

dp[0] = [1]*9

for i in range(1,n) :

  for j in range(9):

    if j == 0 :

      dp[i][j] = dp[i-1][j-1] + i

    elif j == 8 :

      dp[i][j] = dp[i-1][j-1]

    else :

      dp[i][j] =  dp[i-1][j-1] + dp[i-1][j+1]

    print(dp)

print(dp[n-1])

print(sum(dp[n-1])%1000000000)

 

2. 주의사항

첫번째 자리를 기준으로 1~9으로 분류하여 규칙을 찾으려했으나

 

끝 자리 기준으로 0 의 규칙도 고려하여 규칙을 찾아야헀다

 

 

n = 5 까진 j==0 일떄  dp[i-1][j-1] + i 가 성립하지만 n=6 부턴 성립하지 않는다...