쉬운 계단 수 풀이

문제 링크: https://www.acmicpc.net/problem/10844

백준 알고리즘 기초 1/2 400에서 8번째 - 10844번 쉬운 계단 수를 풀어보았다.

 

풀이: dp를 2차원 배열로 만들고, 어떤 수로 시작하는지를 나누어 점화식을 세워야 한다.

 

C++

 

Python

dp=[[0 for i in range(10)] for j in range(101)]
for i in range(1,10): # 1자리수
	dp[1][i]=1
n=int(input())
for i in range(2,n+1):
	for j in range(10):
		if j==0: dp[i][j]=dp[i-1][1] # 0으로 시작
		elif j==9: dp[i][j]=dp[i-1][8] # 9로 시작
		else: dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])%1000000000)

Java