[백준/BOJ] 10844 - 쉬운 계단 수 (c++) (DP)

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

10844번: 쉬운 계단 수

위의 문제는 계단수의 성질와 DP를 이용하여 푸는 문제입니다.

 

맨 앞자리는 0이 오지못한다는 주의할 점도 있습니다.

 

맨뒷자리에 따라 뒤에 올 수 있는 수가 정해져있습니다.

 

맨 뒷자리가

 

0: 1,

1: 0, 2,

2: 1, 3,

...

8: 7, 9,

9: 8

 

이렇게 됩니다. 즉 인접하는 수의 전단계 계단수를 더하면 현재의 계단수를 구할 수 있게되는것입니다.

 

점화식으로 작성해보자면

 

dp[i][j]: 길이가 i이고 마지막 수가 j인 계단수의 개수

 

j=0 이면 dp[i][0] = dp[i-1][1]

j=9 이면 dp[i][9] = dp[i-1][8]

1≤j≤8 이면 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

 

입니다.

---

소스코드

#include <iostream>
#define R 1000000000

using namespace std;

int n, ans, dp[101][10];

int main() {
	cin >> n;
	for (int i = 1; i < 10; i++) dp[1][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < 9; j++) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % R;
		dp[i][0] = dp[i - 1][1];
		dp[i][9] = dp[i - 1][8];
	}
	for (int i = 0; i < 10; i++) ans = (ans + dp[n][i]) % R;
	cout << ans;
}