[BAEKJOON 백준] 10844 쉬운 계단 수 (PYTHON)

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

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

 

이 문제는 DP(다이나믹 프로그래밍) 문제로 한단계씩 진행을 하면서 숫자를 늘려가는 방식으로 문제를 해결했습니다.

 

먼저 N에 문제에서 제시하는 입력값을 받아줍니다.

 

그리고 계단 배열을 만들어주는데, 0~9까지 입력을 받을 배열과 총 100단계까지 있기 때문에 10 X 101으로 배열을 만들어 줍니다.

 

그렇게 만든 배열을 활용을 해서 N층까지 가게 되는데, 첫번째층은 무조건 1~9까지만 1로 넣어줍니다.

그 이후, 2층부터 N층까지 0번부터 시작을 하게 됩니다.

 

그때, 숫자 0으로 올 수 있는 값은 1에서 밖에 없고, 9번의 경우도 8번에서 밖에 없기때문에 따로 처리를 해줍니다.

 

그렇게 나온 값들의 합을 구해서 1000000000을 나눠 출력해 줍니다.

 

N = int(input())
stair = [[0 for i in range(10)] for j in range(101)]	# DP 값들을 넣어줄 배열
for i in range(1, 10):	#1~9까지는 1로 넣어준다. 시작이 0인 것은 없기 때문
    stair[1][i] = 1

for i in range(2, N + 1):
    for j in range(0, 10):
        if j == 0:	# 0일때
            stair[i][j] = stair[i - 1][1]
        elif j == 9:	# 9일때
            stair[i][j] = stair[i - 1][8]
        else:
            stair[i][j] = stair[i - 1][j - 1] + stair[i - 1][j + 1]

print(sum(stair[N]) % 1000000000)