쉬운 계단 수
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
쉬운 계단 수 인데 쉽지가 않더라고요
수학을 잘 못해서, 이런 아이디어를 찾아내는데 시간이 좀 오래 걸렸다. 점화식을 하나 만들고 싶었는데, 그것도 쉽진 않았고, 결국 어쨌든 결과를 찾아내긴 하였다.
자리 수를 표현할 N, 그리고 각 자리에 어떤 수가 들어갈지를 리스트로 표현하여 이차원 리스트로 구현하였다. 예를들어 stairs[3][3]은, 3번째 자리수의 수가 3 이란 소리가 된다. (**3)이런식으로
점화식을 찾기 전에, 각 자리수가 0일 경우, 그리고 9일 경우엔, 케이스가 하나밖에 존재하지 않게 된다. 예를 들어 두번 째 자리수가 0인 3자리 수를 가정하였을 때의 계단수는 101 밖에 없고, 1번째, 3번째 자리수가 0인 경우는 010 말곤 표현할 수가 없고, 9일 경우에도, 2번째는 898, 1,3번째는 989 이런 식으로 밖에 표현하지 못하고, 그 나머지 경우에는 아래의 점화식을 만족하는데,
STAIRS[i][j] = STAIRS[i-1][j-1] + STAIRS[i-1][j+1]
이는 결과 값의 개수를 의미하게 되는데, i번째 자리수가 j인 계단수는,
i-1번째 자리수가 j-1인 계단수 + i-1번째 자리수가 j+1인 계단수 이다.
라는걸 만족하게 된다. 
DP문제들 중에, 이러한 수학적 문제들은 보통 이차원 리스트 내에서의 연관성을 다루는 문제가 많다고, 구글링 하면서 읽은 것 같은데 그 글을 읽고 아이디어를 얻은 문제였다.
코드로 살펴보자
import sys
input = sys.stdin.readline
N = int(input())
stairs = [[0]*10 for _ in range(N+1)]
stairs[1] = [0,1,1,1,1,1,1,1,1,1]
for i in range(2, N + 1):
stairs[i][0] = stairs[i-1][1]
stairs[i][9] = stairs[i-1][8]
for j in range(1,9):
stairs[i][j] = stairs[i-1][j-1] + stairs[i-1][j+1]
cnt = sum(stairs[N])%1000000000
print(cnt)
수학적 지식이나 어떤 사고방식이 잘 갖춰져 있어야 할 것 같은 문제였다.
