[BOJ/Step15] 10844 : 쉬운 계단 수 (Python)

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

1. step[n][m] 에는 m으로 끝나는 n+1자리 계단 수의 개수를 저장할 것이다

2. step[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 이다. ( 한자리 계단수는 1~9 )

3. for문을 통해 2자리부터 n자리까지의 계단수를 구한다

  3-1. n자리 계단수가 0으로 끝나려면 n-1자리 계단수가 1로 끝나야한다

  3-2. n자리 계단수가 t(2~8) 로 끝나려면 n-1자리 계단수는 t-1로 끝나거나 t+1로 끝나야 한다

  3-3. n자리 계단수가 9로 끝나려면 n-1자리 계단수가 8로 끝나야한다

  3-4. 계산한 각 숫자로 끝나는 계단 수를 step 리스트에 추가한다

4. step[n-1] 의 총 합을 1000000000로 나눈 나머지를 출력

 

# 10844.py

n = int(input())

step = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

for i in range(1, n):
    n0 = step[i-1][1]
    n1 = step[i-1][0] + step[i-1][2]
    n2 = step[i-1][1] + step[i-1][3]
    n3 = step[i-1][2] + step[i-1][4]
    n4 = step[i-1][3] + step[i-1][5]
    n5 = step[i-1][4] + step[i-1][6]
    n6 = step[i-1][5] + step[i-1][7]
    n7 = step[i-1][6] + step[i-1][8]
    n8 = step[i-1][7] + step[i-1][9]
    n9 = step[i-1][8]
    step.append([n0, n1, n2, n3, n4, n5, n6, n7, n8, n9])

print(sum(step[n-1]) % 1000000000)