[백준][C++][DP] 10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

 

DP, 동적 계획법은 1차원 방식으로 푸는 문제가 있고 2차원 혹은 그 이상의 차원의 배열을 사용하여 푸는 방식이 있다.

 

이 문제와 같이 마지막 수를 기록해야 하는 경우(연속, 증가 등)에 2차원 배열을 사용한다. 

 

이 문제의 경우 계단수의 몇번째 수인지를 나타내기 위해 n, 마지막 수가 무엇인지를 나타내기 위해 i를 사용하였다. 

 

마지막 수가 0와 9인 경우만 따로 처리를 해주고, 나머지는 점화식을 세워서 풀면 되는 문제

 

 

#include <iostream>

long long memo[101][10] = { 0, };

long long dp(int n, int i)
{
	if (n == 1) return memo[n][i];

	if (memo[n][i] != 0) return memo[n][i];

	if (i == 0) memo[n][i] = dp(n - 1, i + 1);
	else if (i == 9) memo[n][i] = dp(n - 1, i - 1);
	else
	{
		memo[n][i] = (dp(n - 1, i - 1) + dp(n - 1, i + 1)) % 1'000'000'000;
	}

	return memo[n][i] % 1'000'000'000;
}

int main()
{
	for (int i = 1; i < 10; ++i) memo[1][i] = 1;

	int n;
	std::cin >> n;
	long long result = 0;
	for (int i = 0; i < 10; ++i) result = (result + dp(n, i)) % 1'000'000'000;
	std::cout << result;
}