백준 10844. 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

점화식을 잘 세워야 한다는 것을 명심한 문제..

 

i가 숫자열의 길이라고 했을 때, 맨 뒤에 올 수 있는 수의 갯수는 다음과 같다.

이전 i의 대각선의 합으로 나타나는 것으로 알 수 있다.

좌우 끝(1, 9)의 경우에는 대각선 하나의 합으로 나타나고.

 

따라서 점화식을 코드로 구현하면 다음과 같다.

n = int(input())
dp = [[0 for _ in range(10)] for _ 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)