[Baekjoon] 10844번 : 쉬운 계단 수(Python)

Python

방법 1 - 메모리 30864KB / 시간 76ms / 코드 길이 392B

각 숫자의 끝자리를 기준으로 Memorization을 적용한 점화식입니다.

뒷자리가 0일 때 앞에 올 수 있는 숫자는 1뿐입니다. (10)

뒷자리가 9일 때 앞에 올 수 있는 숫자는 8뿐입니다. (89)

나머지 2~8의 숫자가 뒷자리일 때는 2가지의 가능성이 있습니다.

다만 이때 맨 앞의 숫자가 0일 때는 존재하지 않으므로 초기 값을 0으로 설정하여 영향을 주지 않도록 합니다.

D[1][0] = 0

D[1][1] = ... = D[1][9] = 1

이에 따른 점화식은 다음과 같습니다.

0이라는 뒷자리 숫자를 가질 때는 이전 줄(앞의 숫자)의 1의 값을 가지는 값과 동일하다.

9이라는 뒷자리 숫자를 가질 때는 이전 줄(앞의 숫자)의 8의 값을 가지는 값과 동일하다.

2~8의 뒷자리 숫자[j]를 가질 때는 이전 줄(앞의 숫자)의 [j-1]의 값과 [j+1]을 가지는 값과 동일하다.

$$D[i][j] = D[i-1][j-1] + D[i-1][j+1]$$

n = int(input())
D = [[0 for _ in range(10)] for _ in range(n+1)]
for i in range(1,10):
    D[1][i] = 1
for i in range(2,n+1):
    for j in range(10):
        if j == 0:
            D[i][j] = D[i-1][1]
        elif j == 9:
            D[i][j] = D[i-1][8]
        else:
            D[i][j] = D[i-1][j-1] + D[i-1][j+1]    
sumD = 0
for i in range(10):
    sumD += D[n][i]
print(sumD%1000000000)

방법 2 - 메모리 30864KB / 시간 72ms / 코드 길이 257B

방법 1을 조금 더 간소화한 버전입니다.

n = int(input())
D = [[0]*10 for _ in range(n+1)]
D[1]=[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2,n+1):
    D[i][0] = D[i - 1][1]
    D[i][9] = D[i - 1][8]
    for j in range(1,9):
        D[i][j] = D[i-1][j-1] + D[i-1][j+1]
print(sum(D[n])%1000000000)