글 읽기 - 점화식 더 시간 줄일 수 있는 방법 있을까요???

kkyung0321 5년 전 0

탑다운 방식으로 풀었는데 탑다운 함수 안에 for문 돌려도 되는건가요??? 비슷한 문제도 함수안에 for문 넣고 풀었는데 좀 찜찜해서용;;

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

#define mod 10007
int n;

long long cache[1001][10];;

//n자리수에 끝자리가 i인 dp
long long dp(int n, int i);
int main(void) {

	std::cin >> n;
	long long sum = 0;

	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 10; j++) {
			cache[i][j] = 0;
		}
	}

    // 0~9까지의 n자리수를 더하는 for문
	for (int i = 0; i < 10; i++) {
		sum += (dp(n, i) % mod);
	}

	std::cout << (sum%mod);



	return 0;

}


long long dp(int n, int i) {

    //n이 1자리수 이면 더 내려갈곳이 없으므로 반환
	if (n == 1)
		return 1;

	long long &ref = cache[n][i];

	if (ref != 0)
		return ref;

    //이전 자리수보다 한자리 낮게 하고 끝자리는 이전 자리 끝자리와
    //동일할때까지 for문 돌리면서 개수 더함
	for (int j = 0; j <=i; j++) {
		ref+= (dp(n - 1, j)%mod);
	}

	return (ref%mod);

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

점화식 더 시간 줄일 수 있는 방법 있을까요???

kkyung0321 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말