백준10844 - 쉬운 계단 수

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

2차원 DP를 이용하여 푼 문제다. DP의 규칙은 N자리 숫자의 수열의 갯수는 N - 1자리의 숫자들 중에서 끝자리가 1과 8인 경우의 수에 의하여 결정이 된다는 것이다. 

 

ex1.) 2자리 숫자가 21인 경우 3자리 숫자

210, 212

 

ex2.) 2자리 숫자가 32인 경우 3자리 숫자

321, 323

 

ex3.) 3자리 숫자가 878인 경우 4자리 숫자

8787, 8789

 

ex4.) 3자리 숫자가 210인 경우 4자리 숫자

2101

 

ex5.) 4자리 숫자가 8789인 경우 5자리 숫자

87898

 

예제를 보면 끝자리가 1인 경우 0이 나오고 끝자리가 8인 경우 9가 나온다. 여기서 나온 0과 9는 다음 수열에서 사용할 때 1가지 원소밖에 만들어내지 못한다.

 

이렇게 따지면 점화식은 다음과 같다. (N자리 숫자의 끝자리가 L인 경우)

L이 0인 경우: D[N][L] = D[N - 1][1]

L이 9인 경우: D[N][L] = D[N - 1][8]

그 밖의 경우: D[N][L] = D[N - 1][L - 1] + D[N - 1][L + 1]

 

#include <iostream>
using namespace std;

int main() {
	int n, sum = 0;
	int mat[101][10] = { 0 };

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

	cin >> n;

	for (int i = 2; i <= n; i++) { //i는 구할 수열의 길이
		for (int j = 0; j <= 9; j++) { //j는 구할 수열의 끝자리
			if (j == 0) { //구할 수열의 끝자리가 0인 경우
				mat[i][j] = mat[i - 1][1]; //전의 수열 끝자리 1이 결정
			}
			else if (j == 9) { //구할 수열의 끝자리가 9인 경우
				mat[i][j] = mat[i - 1][8]; //전의 수열 끝자리 8이 결정
			}
			else { //그 외의 경우
				//전의 수열 끝자리에서 현재 구하려는 끝자리 숫자보다 +1, -1의 경우 
				mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j + 1];
			}
			mat[i][j] = mat[i][j] % 1000000000; //문제에서 주어진 조건
		}
	}

	//N자리 숫자의 경우의 수 모두 구하기
	for (int i = 0; i <= 9; i++) {
		sum = sum + mat[n][i];
		sum = sum % 1000000000; //문제에서 주어진 조건
	}

	cout << sum;
}