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

BOJ 바로가기

#include <iostream>
#include <math.h>
using namespace std;
int mod = 1000000000;
int d[101][10] = { 0 };
int go(int n, int x);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	long long sum=0;
	for (int i = 0; i < 10; i++)
		sum += go(n, i);
	cout << sum % mod;
	return 0;
}
int go(int n, int x) {
	for (int i = 1; i < 10; i++)
		d[1][i] = 1;
	if (d[n][x])
		return d[n][x];
	if (x == 9)
		d[n][x] = go(n - 1, x - 1) % mod;
	else if ((x == 0) && (n != 1))
		d[n][x] = go(n - 1, x + 1) % mod;
	else if (n!=1)
		d[n][x] = (go(n - 1, x + 1) + go(n - 1, x - 1)) % mod;
	return d[n][x];
}

길이 N이 주어졌을 때 가능한 계단수(앞 숫자와 연속되는 수)의 개수를 구하는 문제이다. 재귀함수를 이용해 코드를 작성해 보았다.

d[a][b]=c 에서 a는 길이, b는 계단수의 마지막 수, c는 b를 포함한 계단수의 개수를 의미한다.

d[n][x] = (go(n - 1, x + 1) + go(n - 1, x - 1)) % mod;

길이가 n이고 마지막 수 x를 포함한 계단수의 개수를 구하기 위해서 길이가 n-1이고 마지막 수 x+1, x-1인 계단수의 개수를 더한다.

for (int i = 0; i < 10; i++)
		sum += go(n, i);

이후 반복문을 이용해 마지막 수를 포함한 계단수의 개수를 모두 더해주면 답을 구할 수 있다.
d[n][x]를 구할 때마다 모듈러 연산을 해서 답의 크기가 너무 커지지 않도록 해준다.