[BOJ/C++] 10844 쉬운 계단

문제

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

풀이

2차원 배열 이용하는 DP !
경우의 수 생각할 때, 앞자리가 1이면 뭐뭐되고, 2면 뭐뭐되고 이런 식으로 생각했는데
이 문제는 마지막 자리에 따라 앞에 오는 경우의 수가 달라지는 거였다.

두 자리인 경우,
마지막 자리 1 : 21
마지막 자리 2 : 12, 32
마지막 자리 3 : 23, 43
마지막 자리 4 : 34, 54
마지막 자리 5 : 45, 65
마지막 자리 6 : 56, 76
마지막 자리 7 : 67, 87
마지막 자리 8 : 78, 98
마지막 자리 9 : 89

정답을 1,000,000,000으로 나눈 나머지를 출력하라고 했으니
✨DP 배열에 저장할 때부터 1,000,000,000으로 나눠서 저장하기

코드

#include <iostream>

using namespace std;

int dp[101][10];

int main() {
	int N;
	int ans = 0;

	cin >> N;
	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0) //마지막 자리가 0이면 앞에 1만 가능
				dp[i][0] = dp[i - 1][j + 1];
			else if (j == 9) //마지막 자리가 9면 앞에 8만 가능
				dp[i][9] = dp[i - 1][j - 1];
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

			dp[i][j] %= 1000000000;
		}
	}

	for (int i = 0; i < 10; i++) {
		ans += dp[N][i];
		ans %= 1000000000;
	}
	cout << ans;

	return 0;
}