백준 10844번 쉬운 계단 수
설명
단순히 점화식을 찾으려고 하면 너무 복잡해진다. 2차원 배열에서의 점화 관계를 사용한다.
위 행렬을 A라고 할 때, A[i][j]는 j로 끝나는 i자리수의 계단의 수이다. 1자리수는 1~9까지 올 수 있으므로 그대로 dp를 채울 수 있고, 2자리수 부터는 0은 전자리수의 1인 경우와 9는 전자리수의 8일 경우이고 나머지는 전자리수의 하나적고 많은 경우의 합이다. 즉 점화식을 dp 배열로 표현하게되면 밑의 코드라고 볼 수 있다.
dp[i][0] = dp[i-1][1]
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
dp[i][9] = dp[i-1][8]코드
import sys
input = sys.stdin.readline
class Solution:
def easy_stair_numbers(self, N: int):
# dp 초기화. 행이 자리수, 열이 0부터 9까지 가능한 개수
dp = [[0,0,0,0,0,0,0,0,0,0] for _ in range(101)]
# dp 처음 1 [0,1,1,1,1,1,1,1,1,1]로 초기화
for i in range(1, 10):
dp[1][i] = 1
"""2번째 부터 0일 수 있는 경우의 수는
전 자리수에서 1인 경우이고,
9인 경우의 수는 전 자리수에서 8인 경우의수임"""
for i in range(2, N+1):
dp[i][0] = dp[i-1][1]
dp[i][9] = dp[i-1][8]
"""1부터 8은 전 자리수에서
n-1, n+1인 경우의 합과 같음"""
for j in range(1, 9):
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
return sum(dp[N])%1000000000
print(Solution().easy_stair_numbers(int(input())))