[Python] 백준 10844 쉬운계단수

코드 작성

dp = [[0 for _ in range(10)] for _ in range(10001)]
for i in range(1,10):
    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]
        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)

코드  풀이

#1 문제 이해

첫 자리수가 n일 경우 그 다음 자리 수는 n+1 또는 n-1이 나올 수 있다.

각 dp의 자리수를 0으로 세팅하고 초기값 1의 자리 수를 세팅한다

dp[1][1] ~ dp[1][9] 0은 올 수 없으므로 제외한다.

그리고 두번째 자리수 dp[2]를 계산할 텐데

0이라는 수가 나오면(i-1) 그 다음 수(i)는 무조건 1만 나올 수 있다.

또는 9라는 수가 나오면(i-1) 그 다음 수(i)는 무조건 8만 나올 수 있다.

그렇지 않으면 i-1에서 j+1의 수 또는 j-1의 수가 나올 수 있다.

#2 코드 이해

dp = [[0 for _ in range(10)] for _ in range(10001)]  # [[0,0,0,0,..0,0], [0,0,0...0]...]
for i in range(1,10):  #초기값 설정, 1부터 9까지
    dp[1][i] = 1
n = int(input())
for i in range(2, n+1):
    for j in range(10): #자리수는 0부터 9까지
        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)