[BOJ] 10844 쉬운 계단 수(다이나믹 프로그래밍)

1. 문제

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

2. 아이디어

DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]

3. 풀이과정

1) ⭕RIGHT⭕

• 코드

#include <iostream>
using namespace std;

#define mod 1000000000
int DP[101][10];

int main() {
	int N;
	long long ans = 0;
	cin >> N;

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

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

	for (int i = 0; i <= 9; ++i) ans += DP[N][i];

	cout << ans % mod << '\n';
	return 0;
}

• 코드 설명
  • int DP[101][10]
    N의 최대값이 100이므로 1~100까지의 인덱스를 쓸 수 있도록 하였고,
    마지막 자릿수로 올 수 있는 숫자는 0~9이여서 이렇게 배열을 생성하였다.