[백준 10844 쉬운 계단 수 문제] PYTHON

조금 어려웠던 문제다.

전 문제에서 규칙을 찾아보자하는 생각을 해서 그런지 틀에 갖혀 생각을 했다.

때로는 노가다도 좋은것 같다.

처음의 접근 방식은 그 전의 N=2일때의 계단 수에 2를 곱하고 -1 을 하면 되지 않을까 했는데

생각을 해보니 0과 9에 도달하는 숫자는 계속 변한다.

그 변하는 숫자의 규칙을 찾기 위해 각각의 숫자 자리에 들어가는 자리의 수를 찾는 등 열심히 했지만

풀지 못했다..

 

그런데 각각의 자리의 수를 구하는 도중 그냥 [k-1][i-1]과 [k-1][i+1]을 더한게 [k][i]인걸 생각해보니

이렇게 푸는 방법도 나쁘지 않아보여 이 방식으로 문제를 해결했다.

 

N = int(input())
dp_before=[0,1,1,1,1,1,1,1,1,1]
dp_after=dp_before[:]

if N==1:
    print(sum(dp_before))
else:
    for i in range(1,N):
        dp_before=dp_after[:]
        for j in range(1,9):
            dp_after[j]=dp_before[j-1]+dp_before[j+1]
        dp_after[0]=dp_before[1]
        dp_after[9]=dp_before[8]
    print(sum(dp_after)%1000000000)