쉬운 계단 수

풀이단계

1. 간단히 N=1일때와 N=2 일때를 계산해보자.
2. 앞에 수가 어덯게 쓰이는가에 따라서 뒤에 수가 결정된다.
3. 이 아이디어에서 점화식을 끌어낼수 있다.
4. 주어진 점화식을 바탕으로 답을 구한다.

DP를 이용한 풀이

dp[n][a] = b // n:숫자길이, a: 마지막으로 끝난 수, b: 숫자길이가 n이고, 마지막으로 끝난수가 a일때 그 숫자의 경우의 수

예를들어 dp[x][0] = dp[x-1][1] 이고
{dp[5][x] : x = 0,1,2,3,4,5,6,7,8,9} = n이 5일때의 경우의 수이다.

코드

#define Moduler 1000000000
#define MAX 100+1
int N;
long long int dp[MAX][MAX];
long long int answer;

int main()
{cin >> N;

	for (int i = 1; i <= 9; i++)
	{
		dp[1][i] = 1;
	}
	dp[1][0] = 0;

	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j==0)
			{
				dp[i][j] = dp[i - 1][j + 1] % Moduler;
			}
			else if (j==9)
			{
				dp[i][j] = dp[i - 1][j - 1] % Moduler;
			}
			else {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] % Moduler;
			}
		}
	}

	for (int i = 0; i < 10; i++)
	{
		answer += dp[N][i];
		answer %= Moduler;
	}
	cout << answer;
}