백준 10844(쉬운 계단 수)

처음에 1차원 dp 배열로 풀려고 했는데 답이 잘 안나와서 한참 헤메다가 2차원 배열이 필요함을 알았다.

 

핵심로직

1. 1차원 dp 로는 풀리지 않기 때문에 각각의 조각에 대한 것을 단계별로 저장을 한다 -> 2차원 배열

 

2. 점화식은 아래와 같다(위의 사진도 참조)

dp[i][x] = dp[i-1][x-1] + dp[i+1][x-1] : (x는 N 으로 가는 수)

 

3. 위의 점화식은 범위를 생각해서 조각을 나눠야 한다.

i == 0 : dp[i][x] = dp[i+1][x-1]

1 <= i <= 9 : dp[i][x] = dp[i-1][x-1] + dp[i+1][x-1]

i == 9 : dp[i][x] = dp[i-1][x-1]

 

#include <iostream>

using namespace std;

int N;
long long dp[10][101];
long long result;

int main(void) {
	for (int i = 0; i < 10; i++)
	{
		if (i == 0) dp[i][1] = 0;
		else dp[i][1] = 1;
	}

	cin >> N;

	for (int x = 2; x <= N; x++)
	{
		for (int i = 0; i < 10; i++)
		{
			if (i == 0) dp[i][x] = dp[i + 1][x - 1];
			else if (i <= 8 && i >= 1) dp[i][x] = (dp[i + 1][x - 1] + dp[i - 1][x - 1])%1000000000;
			else if (i == 9) dp[i][x] = dp[i - 1][x - 1];
		}
	}

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

	cout << result;

	return 0;
}