백준 10844 : 쉬운 계단 수 c++

코드

#include <iostream>
#include <string>

using namespace std;

long long dp[101][10];

int main(){
	
	int N;
	cin >> N;
	
	int mod = 1000000000;
	
	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][1];
			else if(j == 9) dp[i][j] = dp[i-1][8];
			else dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1];
			dp[i][j] %= mod;
		}
	}
	int ans = 0;
	for(int i = 0; i < 10; i++){
		ans = (ans + dp[N][i])%mod;
	}
	
	cout << ans;
	return 0;
}

알게된 점

사람은 생각을 해야한다..

나는 멍청하다..

생각하면 되는것 같다!