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

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

이 문제는 dp 테이블을 2차원 배열로 잡는 방법을 사용하는 문제이다.

먼저 계단 수의 개수 간에 관계를 살펴보면 1~8은 다음 자리 수의 +-1이 되는 수를 유발하고, 0,9는 1,8을 유발한다.

이런 과정을 구현하면 시간 초과이고, 이를 알맞게 dp 테이블에
저장해야 한다.

따라서 dp 테이블을 2차원 배열 dp[100][10]으로 잡았다.

0과 9일 때에는 8에서만 생성되기에 그 부분을 유연히 처리했고,

다른 수들은 전 자리 수의 마지막 수 +-1에서 유발되는

점화식을 작성해주었다.

코드는 다음과 같다.

#include <iostream>
#define MOD 1000000000
typedef long long ll;
using namespace std;

ll dp[100][10];
ll ans=0;
int n;

int main(){
	cin >> n;
	for(int i=1;i<10;i++){
		dp[0][i]=1;
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<10;j++){
			if(j==0){
				dp[i][0]=dp[i-1][1]%MOD;
			}
			else if(j==9){
				dp[i][9]=dp[i-1][8]%MOD;
			}
			else{
				dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%MOD;
			}
		}
	}
	for(int i=0;i<10;i++){
		ans+=dp[n-1][i];
	}
	cout << ans%MOD;
}