백준BOJ 10844 쉬운 계단 수

https://github.com/o920/baekjoon/blob/master/10844.cpp

o920/baekjoon

#include <iostream> 
using namespace std;
int dp[10][101] = { 0, }; //DP[자리수0~9][N]
int main() {
	int N;
	cin >> N; //입력
    
	//초기화 : 0 1 1 1 1 1 1 1 1 1 
	dp[0][1] = 0;
	for (int i = 1; i <= 9; i++) dp[i][1] = 1;
    
    //DP
	for (int j = 2; j <= N; j++) {//두번째자리부터 N번째 자리까지 DP
		for (int i = 0; i <= 9; i++) { // 0부터 9까지 가능한 개수 확인
			if (i == 0) dp[i][j] = dp[i + 1][j - 1]; //0은 그 직전 수가 1일 때밖에 없음
			else if (i == 9) dp[i][j] = dp[i - 1][j - 1]; // 9는 직전 수가 8일 때밖에 없음
			else dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1])%1000000000;
            // 0과 9를 제외한 나머지 수 I가 나오려면 그 직전 수가 I-1 또는 I+1이어야 함
		}
	}
	int sum = 0;
	for (int i = 0; i <= 9; i++) {
		sum = (sum + dp[i][N]) % 1000000000;
	}
	cout << sum << endl;
} 
      
        
        
          o920/baekjoon
          Contribute to o920/baekjoon development by creating an account on GitHub.
          github.com