[BOJ] 백준 10844번 쉬운 계단 수 - 파이썬(Python)

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

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

10844번: 쉬운 계단 수

 

💡 풀이 및 코드

n = int(input())
d = [[0] * 10 for _ in range(n)]

d[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(1, n):
    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]) % 1000000000

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

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 각각은 인접해 있는 수와 결합되어야 하므로, 초기 n=1일 때 계단 수의 개수는 미리 지정한 후 길이 i에 대해 다음과 같은 점화식을 세울 수 있다.

• i = 0 d[i][0] = d[i-1][1]
• i = 9 d[i][9] = d[i-1][8]
• i = j(1~8) d[i][j] = d[i-1][j-1] + d[i-1][j+1]

 

※ 이중리스트 초기화

• 잘못된 표현

d = [[0] * 10] * n  # 출력은 되지만 백준에서 오류

• 정확한 표현

d = [[0] * 10 for _ in range(n)]