[BOJ] 10844. 쉬운 계단 수

문제

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

풀이

 

1. DP[i][j]라고 했을 때 i는 자릿수의 길이를 의미하고 j는 어떤 수의 끝 숫자를 말한다.

2.  i자릿수의 숫자가 j로 끝난다고 하면 그 수의 개수는 i-1자릿수의 j-1로 끝나는 수와 j+1로 끝나는 수의 개수 합이 된다.

3. j가 0일 경우 j-1이 -1이 되서 의미가 없어지고 인덱스를 벗어난다. 즉 j가 0일 경우는 j+1만 해주면 된다.

4. j가 9일 경우 j+1이 10이 되서 의미가 없어지고 인덱스를 벗어난다. 즉 j가 9일 경우는 j-1만 해주면 된다.

---

코드

#include<iostream>
using namespace std;

int DP[101][101];
const int MOD = 1000000000;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	long result = 0;

	for (int i = 1; i <= 9; i++) {
		DP[1][i] = 1;
	}

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) DP[i][j] = DP[i - 1][j + 1] % MOD;
			// j가 0일 경우 j-1이 -1이 되서 의미가 없어지고 인덱스를 벗어난다.
			else if (j == 9) DP[i][j] = DP[i - 1][j - 1] % MOD;
			// j가 9일 경우 j+1이 10이 되서 의미가 없어지고 인덱스를 벗어난다.
			else
				DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % MOD;
		}
	}

	for (int i = 0; i <= 9; i++) result = (result + DP[N][i]) % MOD;
	cout << result;

}