(c++)백준 10844번: 쉬운 계단 수

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

※점화식※

dp[i][j] : 길이가 i인 수의 i번째 자리에 j가 올 때 경우의 수

dp[1][1] ~ dp[1][9]까지 1로 초기화 해준다.

if(j==9) dp[i][j] = dp[i-1][j-1] (마지막 수가 9면 그 앞 숫자는 8만 올 수 있다.)

if(j==0) dp[i][j] = dp[i-1][j+1] (마지막 수가 0이면 그 앞 숫자는 1만 올 수 있다.)

else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] (0과 9 외의 수는 그 앞 숫자로 1 작거나 큰 수가 올 수 있다.)

 

#include <iostream>
using namespace std;
#define D 1000000000

int N;
int dp[101][10];

void DP() {
	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++) {
			//0이전에는 1만 올 수 있음
			if (j == 0)
				dp[i][j] = dp[i - 1][j + 1] % D;
			//9이전에는 8만 올 수 있음
			else if (j == 9)
				dp[i][j] = dp[i - 1][j - 1] % D;
			//아니면 1 크거나 1 작은 수가 옴
			else
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % D;
		}
	}
	long long res = 0;
	for (int i = 0; i <= 9; i++) {
		res += dp[N][i];
	}
	cout << res % D << endl;
}

int main() {
	cin >> N;
	DP();
	return 0;
}