11057 오르막 수

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 10007

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int cache[1005][11];

int func(int start, int len)
{
    if (len == 0)
        return 1;

    int& ref = cache[len][start];
    if (ref != -1)
        return ref;

    ref = 0;
    for (int i = start; i < 10; i++)
        ref = (func(start, len - 1) + ref) % MOD;

    return ref;
}


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

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

    int ans = 0;
    for (int i = 0; i < 10; i++)
        ans = (func(i, n - 1) + ans) % MOD;

    printf("%d", ans);

    return 0;
}

3 넣으면 358이 나오는데 어디서 틀렸어.ㅠ.ㅠㅠㅠㅠ.ㅠ

 

다른 사람 코드 참고해서 봐도 비슷한데 뭐가 문제인지 모르겠다

 

정신 말짱할 때 다시 보면 알겠지 지금은 눈에 안 들어옴

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 10007

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int cache[10][1005];

int func(int start, int N)
{
	if (N == 0) return 1;

	int& ret = cache[start][N];
	if (ret != 0) return ret;

	for (int i = start; i < 10; i++)
		ret += func(i, N - 1) % 10007;

	return ret % 10007;
}

int main()
{
	int N;
	cin >> N;

	cout << func(0, N) << endl;


	return 0;
}

 

헉 아 또 갑자기 생각났는데 MOD 문제 아님??? 

 

하지만 나중에 고쳐봄