백준 10844 쉬운 계단 수 (C++)

10844번: 쉬운 계단 수

N이 주어졌을 때, N 자릿수에 해당하는 계단수의 갯수를 찾는 문제이다. N=2라고 생각해보자. 첫째 자리가 3일 경우, 둘째 자리에 올 수 있는 수는 2, 4이다. 즉 23, 43이다. N=3이면 둘째 자리는 2,4이고 2일 경우 셋째 자리는 1,3, 4일 경우 셋째 자리는 3,5이다. 즉 123, 323, 343, 543이다. 이를 점화식으로 나타내면 다음과 같다. x는 0 ~ 9 수이다

• dp[N][x] = dp[N-1][x-1] + dp[N-1][x+1]

dp[N]에 모든 경우의 수가 있으므로 반복문으로 모두 합하여 나머지를 출력한다.

#include <iostream>

using namespace std;

int N;
long long res = 0;
long long dp[101][10];

void solution() {
	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][j + 1];
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			}

			dp[i][j] %= 1000000000;
		}
	}

	for (int i = 0; i < 10; i++) {
		res += dp[N][i];
	}

	cout << res % 1000000000;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	solution();
	
	return 0;
}