10844
BOJ 10844 쉬운 계단 수
boj 10844 쉬운 계단 수 길이가 N인 계단 수의 경우의 수를 어떻게 나눌 수 있을까. 맨 끝의 숫자가 0~9 중 하나인 것은 자명하다. 맨 끝의 숫자가 0일 경우를 생각해보면, 계단 수이므로 0 앞의 수는 1만 가능하다. 즉, 길이가 N-1이고 끝이 1인 계단 수만이 0 앞에 올 수 있다는 의미이다. 맨 끝의 숫자가 9인 경우는, 9 앞의 수로 8만 올 수 있다. 남은 경우인 맨 끝의 숫자가 1부터 8 사이의 경우는, 각 수에서 1씩 더하거나 뺀 수들이 앞에 올 수 있다. 이 내용을 점화식으로 나타내보자. 테이블로 D[i][j]는 길이가 i이고 맨 끝 수가 j인 계단 수의 갯수라고 한다. j가 0 일 때, D[i][j] = D[i-1][j+1] j가 9 일 때, D[i][j] = D[i-1][j-..