[백준] 10844 파이썬(python) : 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

 

dp테이블을 2차원으로 설정해서 "dp[자리 수][현재 위치] = 앞자리에 올 수 있는 숫자 개수"로 지정한다. 맨 앞자리의 0이 오는 경우는 올 수 없으므로 0으로 설정하고 n=1일때(자리 수 1일때)의 1~9의 숫자는 모두 1이 된다. 두번째 자리 부터는 숫자 0은 앞 자리에 1만 올 수 있고 숫자 9는 앞자리에 8만 올 수 있다. 그래서 다른 경우들과 다르게 2가지는 따로 분류를 해준다.

 

import sys
n = int(sys.stdin.readline())
dp = [[0]*10 for _ in range(n+1)] #1
for i in range(1, 10): #2
    dp[1][i] = 1

for i in range(2, n+1): #3
    for j in range(10): #4
        if j == 0: #5
            dp[i][j] = dp[i-1][1]
        elif j == 9: #6
            dp[i][j] = dp[i-1][8]
        else: #7
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[n]) % 1000000000) #8

 

#1 : dp테이블은 2차원으로 설정한다

#2 : 첫번째 자리 dp[1]의 원소 0빼고 모두 값을 1로 설정

#3, 4 : 두번째 자리부터 시작해서 각 숫자 (0~9)마다 반복

#5 : 숫자가 0일때 이전자리의 1번째 인덱스의 원소 가져옴

#6 : 숫자가 9일때 이전자리의 8번째 인덱스의 원소 가져옴

#7 : 모두 아닌 경우엔 dp[i-1][j-1]와 dp[i-1][j+1]의 원소를 더해줌

#8 : n번째 자리에 올 수 있는 모든 수를 더하면 n줄에서의 계단 수의 개수를 구할 수 있다.

 

비슷한 문제가 있어서 가져왔다.

https://hgk5722.tistory.com/200

[백준] 1932 파이썬(python) : 정수 삼각형