빡대갈 머리로는 도저히 이해를 할 수 없어 이런식으로 계속 노가다함...

그러다가 발견한게 무조건 양옆의 합이 홀수라는 점을 발견함..

그래서 이것을 BFS나 Dijkstra 가중치를 생각을 했는데 대가리가 너무 아파서 포기하고 구글링을 함.

https://yabmoons.tistory.com/22
(여기보고 참고해서 글로 적으면서 정리함.)

요약하면 위와 같음.

근데 이것을 코드로 또 짜내는 것은 별개의 문제인듯 하다.

C++코드 (내가 짠거)

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

#define endl "\n"
#define MAX 101
#define Moduler 1000000000

unsigned long long cache[MAX][11];
int n;

long long Stair(int numberSize, int endNumber)
{
	// 기저
	if (numberSize == 1)
		return cache[numberSize][endNumber];

	// 캐시
	unsigned long long& ret = cache[numberSize][endNumber];
	if (ret != 0) return ret;

	// 구함
	if (endNumber == 0)
		return ret = Stair(numberSize - 1, endNumber + 1) % Moduler;
	else if (endNumber == 9)
		return ret = Stair(numberSize - 1, endNumber - 1) % Moduler;
	else
		return ret = ( Stair(numberSize - 1, endNumber - 1) + Stair(numberSize - 1, endNumber + 1) % Moduler );
}

int main()
{
	memset(cache, 0, sizeof(cache));
	cin >> n;

	cache[1][0] = 0;
	for (int i = 1; i < 10; ++i)
		cache[1][i] = 1;

	unsigned long long sum = 0;
	for (int i = 0; i < 10; ++i)
		sum += Stair(n, i);
	cout << sum % 1000000000;

	return 0;
}

좀 지저분 하고 더러운거 같다. 아직 DP를 잘모르는 사람이 코드를 작성한 티가 ㅈㄴ 남.

또한 내코드는 시작점?을 main함수에서

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

이런식으로 입력받은 수에서 0~9까지 시작점을 잡아 주어야 돌아가는 애송이 코드임.

남이 짠거

이부분은 그냥 제출 현황에서 메모리적게 쓰고 코드 길이 나보다 절반정도 짧은 사람꺼 긁어옴

https://www.acmicpc.net/source/52757767

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

long long int d[101][10];

int main() {
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= 9; i++) {
		d[1][i] = 1;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j - 1 >= 0)
				d[i + 1][j - 1] += d[i][j] % 1000000000;
			if (j + 1 < 10)
				d[i + 1][j + 1] += d[i][j] % 1000000000;
		}
	}

	long long int res = 0;
	for (int i = 0; i < 10; i++) {
		res += d[N][i];
	}
	printf("%lld\n", res % 1000000000);

	return 0;
}