[백준] 10844 in Python 파이썬 풀이

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

쉽지않은 계단수 문제였따 ..

 

여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다.

규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다.

즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 

끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 

 

자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. 그래야 그 이후부터 연산을 할 수 있기 때문이다 

n = int(input())
dp = [[0 for i in range(10)] for j in range(101)]

for i in range(1, 10):
    dp[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

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