백준 10844 : 쉬운 계단 c++

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

나는 왜이렇게 dp가 어려울까...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
	int dp[101][10]; // 번째 , 0~9
	int n;
	int sum=0;
	cin >> n;

	dp[1][0] = 0;

	for (int i = 1; i <= 9; i++)
	{
		dp[1][i] = 1;
	}
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j == 0)
			{
				dp[i][0] = dp[i - 1][1]; //이전께 1인거만 다음에 0 붙기 가능
			}
			else if (j==9)// 1~8
			{
				dp[i][9] = dp[i - 1][8];//이전께 8인거만 다음에 9 붙기 가능
			}
			else
			{
				dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])% 1000000000;
			}
		}
	}

	for (int i = 0; i <= 9; i++)
	{
		sum = (sum+dp[n][i])% 1000000000;
	}
	cout << sum % 1000000000 << endl;
	return 0;

}