https://www.acmicpc.net/problem/11057

뭐 이런 문제인데 이전 문제 "쉬운 계단 문제"랑 거의 똑같은 문제이다.

https://velog.io/@starkshn/%EB%B0%B1%EC%A4%80-10844-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EB%AC%B8%EC%A0%9C-DP

근데 나는 거의 두시간 투자해도 못풀고 언리얼 공부하다가 저녁쯤에 다시하니까 풀렸음...

역시 빡대가리라 하나하나 다적어가면서 규칙을 찾을려고 애를 썻음..

그러다가 코드에다가 자릿수가 2자리이고 끝자리가 3인경우를 생각을 해서 주석으로 달아보면서 생각하니까 이해가 되었음.

cache[2][3]
cache[1][0] + cache[1][1] + cache[1][2] + cache[1][3]

아 그러면 3자리인데 끝자리가 3인경우는?

cache[3][3]
cache[2][0] + cache[2][1] + cache[2][2] + cache[2][3] 

이거 아니겠나? 왜냐하면

수가 이렇게 있을 때 자리가 3자리이고 뒷자리가 3인 경우는

2자리 숫자이고 뒷자리가 0 + 2자리 숫자이고 뒷자리가 1 + 2자리 숫자이고 뒷자리가 2 + 2자리 숫자이고 뒷자리가 3임

즉,

cache[3][3]
cache[2][0] + cache[2][1] + cache[2][2] + cache[2][3] 

이렇게 됨.

CPP 코드

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

#define MAX 1001
#define Moduler 10007

int cache[MAX][10];

int DP(int numberSize, int lastNumber)
{
	// 기저
	if (numberSize <= 1) return cache[numberSize][lastNumber];

	// 캐시
	int& ret = cache[numberSize][lastNumber];
	if (ret != 0) return ret;

	// 구한다
	for (int i = 0; i <= lastNumber; ++i)
	{
		ret += DP(numberSize - 1, i);
	}

	ret %= Moduler;
	return ret;
}

int main()
{
	memset(cache, 0, sizeof(cache));
	
	for (int i = 0; i < 10; ++i)
	{
		cache[0][i] = 0;
		cache[1][i] = 1;
	}

	int n;
	cin >> n;
	int ret = 0;

	for (int i = 0; i < 10; ++i)
	 ret += DP(n, i);

	cout << ret % Moduler;

	return 0;
}