[백준 / BOJ] 10844번: 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

 

---

 

코드

---

#include <iostream>
using namespace std;
# define mod 1000000000
int main() {
	int n, dp[101][11] = {}, sum = 0;
	cin >> n;

	for (int i = 1; i <= 9; i++) dp[1][i] = 1;

	for (int i = 2; i <= n; i++) {
		dp[i][0] = dp[i - 1][1];
		dp[i][9] = dp[i - 1][8];
		for (int j = 1; j <= 8; j++) 
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
	}

	for (int i = 0; i <= 9; i++) {
		sum = (sum + dp[n][i]) % mod;
	}

	cout << sum << "\n";
	return 0;
}

 

 

 

---

 

 

문제에서, 45656처럼 인접한 모든 자리의 차이가 1인 수를 쉬운 계단 수라고 지칭한다고 하였다. 풀이 방법이 잘 생각나지 않아 다른 사람들의 풀이 방법을 참고했다. 쉬운 계단 수의 특징은 다음과 같다.

1. 일의 자리 수가 0이면, 십의 자리에는 1만 올 수 있다. 
2. 일의 자리 수가 9이면, 십의 자리에는 8만 올 수 있다.
3. 일의 자리 수가 0과 9를 제외한 수 i라면, 십의 자리 수에는 i-1 또는 i+1이 올 수 있다.

길이가 n인 쉬운 계단 수의 갯수를 구하려면 일의자리가 0인 경우의 쉬운 계단 수의 갯수에서 9인 경우의 쉬운 계단 수의 갯수까지 모두 더해주면 된다. 만약, 길이가 n인 쉬운 계단 수에서 일의 자리 수가 각각 0, 9라면 길이가 n-1인 쉬운 계단 수에서 일의 자리 수가 각각 1, 8인 경우와 구하는 갯수가 같다. 길이가 n인 쉬운 계단 수에서 일의 자리 수가 0과 9를 제외한 i라면, 길이가 n-1인 쉬운 계단 수에서 일의 자리 수가 각각 i-1, i+1인 경우의 갯수를 더한 값이 구하는 갯수이다.