글 읽기 - TL해결하고 싶습니다.

scared22 5년 전 0

dp를 써서 구현했는데 TL이 떠서 어떻게 하면 TL을 벗어날 수 있는 알고 싶습니다 .

#include <cstdio>

int n, m;

long long result, dp[1005][1005];

long long solve(int pos, int sum)
{
	if (pos == m)
	{
		if (sum == n) return 1;
		return 0;
	}

	long long &ret = dp[pos][sum];

	if (ret != 0) return ret;

	for (int i = 1; i <= 3; i++)
	{
		ret += solve(pos + 1, sum + i);
	}

	return ret;
}

int main()
{
	int t;

	scanf("%d", &t);

	for (int i = 0; i < t; i++)
	{
		scanf("%d %d", &n, &m);

		printf("%lld\n", solve(0, 0) % 1000000009);

		for (int j = 0; j<1005; j++)
		{
			for (int k = 0; k<1005; k++)
				dp[j][k] = 0;
		}
	}
}

djm03178 5년 전 0

dp를 역순으로 하지 말고 solve(n, m)이 n, m에 대한 답을 구하게끔 해보세요. 그러면 매 케이스마다 dp를 초기화하지 않고 그대로 solve만 호출해도 됩니다.

scared22 5년 전 1

조언 덕분에 재귀공부를 제대로 할 수 있었습니다 .

이 두개의 차이점을 알고 싶습니다.

1번은 맞았지만 2번은 시간초과가 발생했습니다.

2번에서 재귀호출을 하게 되면 기존에 누적된 값이 있으면 바로 반환할 수 있어서 TL이 안뜰꺼라 생각했지만 발생 했습니다. 그이유를 알고 싶습니다.

//1번
	for (int i = 3; i <= 1000; i++)
	{
		for (int j = 1; j <= 1000; j++)
		{
			if (i - 1 < 0) dp[i][j] = 0;
			else if (i - 2 < 0) dp[i][j] = ((long long)dp[i - 1][j - 1]) % (int)(1e9 + 9);
			else if (i - 3 < 0) dp[i][j] = ((long long)dp[i - 1][j - 1] + dp[i - 2][j - 1]) % (int)(1e9 + 9);
			else dp[i][j] = ((long long)dp[i - 1][j - 1] + dp[i - 2][j - 1] + dp[i - 3][j - 1]) % (int)(1e9 + 9);
		}
	}
//2번 
long long solve(int num, int jari)
{
	if (num < 0) return 0;

	if (num == 0 && jari > 0) return 0;

	if (jari == 0)
	{
		if (num == 0) return 1;
		return 0;
	}

	long long &ret = dp[num][jari];
	if (ret != 0) return ret;

	for (int i = 1; i <= 3; i++)
	{
		ret += solve(num - i, jari - 1);
	}

	return ret % 1000000009;
}

djm03178 5년 전 0

혹시 dp를 케이스마다 초기화하셨나요?

scared22 5년 전 0

아뇨 초기화 하지 않았습니다.

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

문제

문제

출처

ICPC

TL해결하고 싶습니다.

scared22 5년 전 0

djm03178 5년 전 0

scared22 5년 전 1

djm03178 5년 전 0

scared22 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말