백준 10844번 쉬운 계단 수 [ Java ]

10844번: 쉬운 계단 수

3가지 경우를 나누어 생각했습니다.

1. 맨 앞자리가 1일 때
2. 맨 앞자리가 9일 때
3. 맨 앞자리가 2~8일 때

 

1. 맨 앞자리가 1일 때

1의 경우는 바로 뒤의 0도 나올 수가 있기 때문에 9가 나올 경우와는 조금 다릅니다.

- 1뒤에 0이 나올 때는 뒤에 무조건 1밖에 올 수 없습니다. (첫 번째 숫자가 1일 때 세 번째 숫자는 무조건 1일 경우)
-> A(n-2)[1]

- 1뒤에 2가 나올 경우 (첫 번째 숫자가 1이면서 두 번째 숫자가 2일 경우)
-> A(n-1)[2]

2. 맨 앞자리가 9일 때

9뒤에는 무조건 8이 나오기 때문에 이전항에서 8이 나온 경우만 넣어주면 됩니다.
-> A(n-1)[8]

3. 맨 앞자리가 2~8일 때

현재 숫자 뒤에 현재 숫자보다 1 작은수의 경우 + 1 큰 수의 경우
-> A(n-1)[now-1] + A(n-1)[now+1]