[백준][Python] 10844번 쉬운 계단 수

10844번: 쉬운 계단 수

코드

n = int(input())
dp = [[0]*10 for _ in range(n+1)]

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)

 

설명

n이 1일 때는 0을 제외한 1~9까지의 숫자가 올 수 있다.

n이 2일 때는 앞의 숫자가 9일 때를 제외하면 뒤에 올 수 있는 숫자는 두 가지이다.

dp 배열에 경우의 수를 저장해나간다. i는 자릿수를 의미하고 j는 앞의 숫자를 의미한다. 따라서 j가 0일 때는 뒤에 1밖에 오지 못하기 때문에 dp[i-1][1]과 경우의 수가 같다. j가 9일 때도 마찬가지고 나머지 경우에는 뒤에 올 수 있는 숫자가 두 가지이기 때문에 dp[i-1][j-1]+dp[i-1][j+1]이다.