[10844] 쉬운 계단 수

• 입력: 자릿수 N
• 출력: 자릿수 N의 계단수 개수

계단 수란 45656 처럼 인접한 모든 수가 1차이가 나는 수이다

• 알고리즘: 동적계획법
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<vector<int> > stair(n, vector<int>(10, 0)); //한 자릿수 초기화 for (int i = 0; i < 10; i++) stair[0][i] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < 10; j++) { if (j != 9) stair[i][j] = stair[i - 1][j + 1] ; if (j != 0) stair[i][j] = (stair[i][j] + stair[i - 1][j - 1]) % 1000000000; } } int cnt = 0; for (int i = 1; i < 10; i++) cnt = (cnt + stair[n - 1][i]) % 1000000000; printf("%d\n", cnt); return 0; }

앞자리가 i인 n 자릿수의 계단수는 앞자리가 (i - 1)과 (i + 1)의 (n - 1) 자릿수의 계단수를 합친 것과 같다. 단, 앞자리가 0이면 다음 수는 무조건 1이여야하고, 앞자리가 9이면 다음 수는 무조건 8이여야한다. 이 경우를 제외시키고는 모두 동일하다.

문제에서 앞자리가 0일 수 없다고 했으므로 답을 유추할 때는 1~9까지 합하여 출력하면 된다. 

• 문제 참고: https://www.acmicpc.net/problem/10844