백준 10844 C++ - 쉬운 계단 수

Intro

문제해결 및 소스코드

#include <iostream>

using namespace std;

/*									<문제해결>
			규칙1. 계단수는 인접한 모든 자리의 차이가 1이다.
			규칙2. 길이가 N(1~100)인 계단수는 몇개인지 구하되, 정답을 10억으로 나눈 나머지를 출력하라.

			이 문제를 풀기위해 규칙성을 먼저 찾고자했다.
			길이가 1인 계단수 : 1, 2, 3, 4, 5, 6, 7, 8, 9	
			길이가 2인 계단수 : 10,12  21,23  32,34  43,45  54,56  65,67  76,78  87,89  98
			길이가 3인 계단수 : 101  121,123  210,212 ...

			이정도 쓰고나니 규칙이 보였다. 길이가 N인 계단수를 만들기위해서는 길이가 N-1인 계단수에서 마지막 자릿수를 +1 또는 -1한 수를 붙여주면 되었다.
			하지만 주의해야할 점이 끝자리수가 0또는 9이면 다음 올수있는 수는 하나뿐이다.

			따라서 이문제는 DP를 이용하여 풀었고, 테이블을 dp[i][j] : 길이가 i인 끝자리수가 j로 끝나는 수의 갯수로 설정했다.
			예를들어, dp[2][3]은 길이가2이고, 끝자리가 3으로끝나는 수의 갯수이다.
			dp[2][3]은 23, 43이 있다. 이는 길이가 1이며 끝자리가 2또는 4인 수의 경우를 더한것이다.

			따라서 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 점화식을 구할 수 있다. 
			또한 끝자리가 0 또는 9일 경우 예외규칙을 두어야하므로,
			j == 0 : dp[i][j] = dp[i][j+1]
			j == 9 : dp[i][j] = dp[i][j-1] 이 된다.

			길이가 1인 수를 기저값으로 설정해준다면
			dp[1][1] ~ dp[1][9] = 1이다.
*/

int dp[101][10];

int main()
{
	int n;
	cin >> n;

	// .. 기저값 설정
	for (int i = 1;i < 10;i++)
	{
		dp[1][i] = 1;
	}
	
	// .. 테이블 채우기
	for (int i = 2;i <= n;i++)
	{
		for (int j = 0;j < 10;j++)
		{
			if (j == 0) dp[i][j] = dp[i - 1][j + 1];
			else if (j == 9) dp[i][j] = dp[i - 1][j - 1];
			else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

			dp[i][j] %= 1000000000;
		}
	}

	int sum = 0;					
	// .. 정답은 dp[n][1] ~ dp[n][9]를 모두 더하여 10억으로 나눈 수
	for (int i = 0;i < 10;i++)
	{
		sum = (sum + dp[n][i]) % 1000000000;
	}

	cout << sum;
}