[BOJ] 백준 10844 쉬운 계단 수 (Swift)

문제

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

10844번: 쉬운 계단 수

풀이

N이 1일 때는 1...9 까지의 수가 계단 수 입니다.

N이 2일 때 앞의 자리가
1인 경우, 0 2
2인 경우, 1 3
3인 경우, 2 4
4인 경우, 3 5
..
7인 경우, 6 8
8인 경우, 7 9
9인 경우, 8

N이 2일때, 끝나는 수가 0과 9가 아닌경우는 2번씩 등장하게 됩니다.
예를 들어 끝나는 수가 3인 경우, 앞의자리가 2일때와 4일때 2번 등장합니다.

정의 : $f(n, d)$ = 길이가 n, 마지막 자리의 수가 d인 계단수
구하는 답 : $f(n,0) + f(n,1) + ... + f(n, 9)$
초기값 : $f(1, 0) = 0, f(1, 1 ~ 9) = 1$
점화식 : $f(n, d)$ =
$if \ \ \ d == 0, \ \ \ f(n - 1, 1)$
$elif \ \ \ d == 9, \ \ \ f(n - 1, 8)$
$else \ \ \ f(n - 1, d - 1) + f(n - 1, d + 1)$

이게 길이가 n이고 마지막 숫자가 0~9까지인 계단 수 갯수를 출력시켜주면 됩니다.

소스코드

후기

어려웠던 문제였습니다.
정의도 떠올리는것이 어려웠습니다.
단순히 수학식으로 구할 수 있을 줄 알았는데 다이나믹 프로그래밍 기법을 사용했어야 했던 문제였습니다.