쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자릿수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

예제 입력 및 출력

입력

2

 

출력

17

소스 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
long long cache[101][11]; //cahce[length][num] 길이가 length이고 num으로 시작하는 계단 수 개수

long long stairnum(int N, int num) {
	if (cache[N][num] != -1)
		return cache[N][num];

	if (N == 1) {
		return cache[1][num] = 1;
	}

	int count = 0;

	if (num + 1 != 10)
		count += stairnum(N - 1, num + 1);
	if (num - 1 != -1)
		count += stairnum(N - 1, num - 1);


	return cache[N][num] = count % 1000000000;
}

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

	memset(cache, -1, sizeof(cache));

	for (int i = 1; i <= 9; i++)
		total += stairnum(N, i);
	
	cout << total % 1000000000;
}

문제 풀이

 1. cache값 설정

• cache[length][num] : 길이가 length이고 num으로 시작하는 계단 수의 개수

 2. 함수 탈출 조건

• 인자로 전달받은 길이가 1이면 계단수는 1개밖에 존재하지 않으므로 1 반환

 3. 재귀 함수 호출

• 현재 숫자가 9가 아니라면 길이가 1 줄고 현재 숫자+1로 시작하는 계단 수 개수를 세어준다 : stairnum(N-1, num+1)

• 현재 숫자가 0이 아니라면 길이가 1줄고 현재 숫자-1로 시작하는 계단 수 갯수를 세어준다 : stairnum(N-1, num-1)

 

문제 출처 : https://www.acmicpc.net/problem/10844