10844) 쉬운 계단 수 c++

문제 ) www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

풀이 ) 이번 문제는 11057 오르막 수와 비슷했다.

1. 0으로 시작하는 수가 없으므로 수의 길이 N = 1 일때,
   dp[1][1~9] 의 값에 모두 1을 대입한다.

2. 수의 길이 N >= 2 라면 조금 생각이 필요하다.

계단 수란, "인접한 모든 수의 차이가 1"이라고 했다. 

3. 그렇다면 두 자리 수에서 0 다음에 올 수 있는 숫자는 뭐가 있을까? 1 밖에 없다.

4. 그럼 9 다음에 올 수 있는 숫자는? 8 밖에 없다.

5. 1~8의 경우에는 다 2개의 수가 올 수 있다.
   예를 들어, 1의 경우는 0,2 가 올 수 있다.

그래서 3,4,5 번 의 경우를 따로 생각해줘야 했다.

 

6. 마지막으로 dp 배열에 들어간 모든 수를 더해서 MOD = 1,000,000,000으로 나눈 나머지를 출력하면 된다.

 

코드 ) 

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

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

int main(int argc, char** argv) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	
	for(int i=1; i<10; i++) {		// 1
		dp[1][i] = 1;
	}
	
	for(int i=2; i<=N; i++) {		// 2
		dp[i][0] = dp[i-1][1] % MOD;	// 3
		dp[i][9] = dp[i-1][8] % MOD;	// 4
		for(int j=1; j<=8; j++) {	// 5
			dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD;
		}
	}
	
	for(int i=0; i<10; i++) {		// 6
		sum = (sum + dp[N][i]) % MOD;
	}
	
	cout << sum;
	return 0;
}