[BAEKJOON 10844번] (C++) 쉬운 계단 수

 

 

www.acmicpc.net/problem/10844

2차원 배열 dp[x][y]에 sol[x][y]의 결과를 저장하고

이미 방문하여 계산을 마친 [x,y] 는 사전에 저장해놓은 dp[x][y]를 사용하여 계산해 반복 계산을 줄인다.

계단 수의 경우의 수는 한칸 아래 혹은 한칸 위 뿐이므로 가장 작은 수 0과 가장 큰 수 9를 예외로 두고

if (x == 0)
dp[x][y] += sol(x + 1, y + 1);
else if (x == 9)
dp[x][y] += sol(x - 1, y + 1);
else {
dp[x][y] += sol(x - 1, y + 1);
dp[x][y] += sol(x + 1, y + 1);
}

다음과 같은 형식으로 재귀 형태로 구성하며

if (y == n - 1) {
dp[x][y] = 1;
return dp[x][y];
}

가장 높은 자릿수에서는 더이상 반복하지 않고 1 을 return 한다.

 

코드

#include<iostream>
#define MAX 101
#define N 10

using namespace std;
long long dp[N][MAX] = { 0 };
int n;

long long sol(int x, int y) {
	//이미 방문한 경우
	if (dp[x][y] != 0)
		return dp[x][y];
	//기저
	if (y == n - 1) {
		dp[x][y] = 1;
		return dp[x][y];
	}

	if (x == 0)
		dp[x][y] += sol(x + 1, y + 1);
	else if (x == 9)
		dp[x][y] += sol(x - 1, y + 1);
	else {
		dp[x][y] += sol(x - 1, y + 1);
		dp[x][y] += sol(x + 1, y + 1);
	}

	return dp[x][y] % 1000000000;
}


int main() {
	cin >> n;
	long long sum = 0;
	for (int i = 1; i < 10; i++)
		sum += sol(i, 0);

	cout << sum % 1000000000 << endl;
	return 0;
}

 

결과