[BOJ10844] 쉬운 계단 수

N자리 계단 수 총 개수

• 45656은 계단수 (모든 자리수가 1차이)
• 길이 N인 계단 수 몇 개?

입력

• N (1<= <= 100)

출력

• 계단수 개수를 1,000,000,000으로 나눈 나머지

설계

• 1의 자리에 -1, +1을 하여 계단 수 구현
• dp[i][j] : (i : n자리 / j : 1의 자리의 수) i, j에 해당하는 계단 수 갯수
• dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod
• 하지만, 1의 자리가 0과 9일 때, +1과 -1의 계산으로 계단수를 구할 수밖에 없음 ex) 현재 1의 자리 0일 경우 —> 이전의 1의 자리는 1만 가능 현재 1의 자리 9일 경우 —> 이전의 1의 자리는 8만 가능
• 위 조건을 고려하여 알고리즘 구현

How I solved(click to github)

---

ref :
BOJ10844