[BOJ] 10844 - 쉬운 계단 수

안녕하세요.

여행벌입니다.

오늘은 BOJ 10844번 쉬운 계단 수 문제를 풀어보겠습니다.

---

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

10844번: 쉬운 계단 수

[알고리즘풀이]

Dp[i][j] : i 길이를 가진 계단 수 중 j를 끝으로 하는 수의 갯수.

ex) 길이가 2인 계단 수는 10 / 12 / 21 / 23 / ⋯ / 87 / 89 / 98 이므로

Dp[2][0] = 1, Dp[2][1] = 1, Dp[2][2] = 2 , ⋯ Dp[2][9] = 1 이 성립한다.

이때, 길이가 3이고 끝이 4인 계단 수를 생각해보자. 길이가 2이고 끝이 3 또는 5인 계단수에서 길이가 3이고 끝ㅇ이 4인 계단 수를 만들 수 있으므로 다음과 같은 식이 성립한다.

▶ Dp[i][j] = Dp[i-1][j-1] + Dp[i-1][j+1]

#include<iostream>

using namespace std;

int dp[101][10];

int main(void) {
	for (int i = 1; i < 10; i++)
		dp[1][i] = 1;
	for (int i = 2; i < 101; 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]) % 1000000000;
		}
	}
	long long n, answer = 0;
	cin >> n;
	for (int i = 0; i < 10; i++)
		answer += dp[n][i];
	cout << answer % 1000000000;
}

---