글 읽기 - 동적계획법 재귀 둘다 시간초과가 떠서 둘이 섞어봤는데도 시간초과가 뜨네요.

mkleeboy3 5년 전 0

어떻게 수정하면 좋을까요. 일부러 목표 건물로 가는 경로에 있는 것들만 재귀적으로 돌고 메모이제이션으로 dp값이 있는 경우는 재귀를 하지 않고 dp참조를 하게끔 했는데 안되네요.

/*
2019-02-26
Lee Min Keon
Baekjoon Online Judge #1005
mkleeboy3@naver.com
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct rel
{
	int* parents;
	int len;	
} rel;	

void init_rel(rel* r, int n)
{
	r->parents = (int*)calloc(n, sizeof(int));
	r->len = 0;
}	

int f(int n, int* dp, int* weight, rel* child)
{
	if (n == 0) return 0;

	int max = 0;

	for (int i = 0; i < child[n].len; i++)
	{		
		int temp = (dp[child[n].parents[i]] == -1) ? f(child[n].parents[i], dp, weight, child) : dp[child[n].parents[i]];

		if (temp > max) max = temp;
	}
	
	dp[n] = max + weight[n];
	return max + weight[n];
}

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

	int* result = (int*)calloc(test_case, sizeof(int));
	int result_index = 0;

	for (int ttc = 0; ttc < test_case; ttc++)
	{
		int n, rules;
		scanf("%d %d", &n, &rules);
		
		int* dp = (int*)calloc(n + 1, sizeof(int));
		for (int td = 0; td < n + 1; td++)
			dp[td] = -1;

		int* weight = (int*)calloc(n + 1, sizeof(int));
		for (int tn = 0; tn < n; tn++)
			scanf("%d", &weight[tn + 1]);
		
		rel* child = (rel*)calloc(n + 1, sizeof(rel));
		for (int tr = 0; tr < n; tr++)
			init_rel(&child[tr + 1], rules);
		
		for (int tr = 0; tr < rules; tr++)
		{
			int p, c;
			scanf("%d %d", &p, &c);
			
			child[c].parents[child[c].len++] = p;
		}

		int obj;
		scanf("%d", &obj);

		result[result_index++] = f(obj, dp, weight, child);
		
		free(dp);
		free(weight);
		for (int tr = 0; tr < n; tr++)
			free(child[tr + 1].parents);
		free(child);
	}

	for (int i = 0; i < result_index; i++)
		printf("%d\n", result[i]);

	free(result);
}

mkleeboy3 5년 전 1

malloc, calloc, realloc, free와 같은 시스템콜을 저렇게 써버릇하면 코드 실행이 느려져서 시간초과가 뜨는 거였군요. 알고리즘은 문제없이 잘 돌아갑니다. 전역변수로 다 바꾸고 free대신에 초기화 과정을 넣어주니까 해결했습니다.

/*
2019-02-26
Lee Min Keon
Baekjoon Online Judge #1005
mkleeboy3@naver.com
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct rel
{
	int parents[1001];
	int len;
} rel;

rel child[1001];
int weight[1001];
int dp[1001];

void init_rel(rel* r)
{
	for (int i = 0; i < 1001; i++)
		r->parents[i] = 0;
	r->len = 0;
}

int f(int n, int* dp, int* weight, rel* child)
{
	if (!child[n].len) return weight[n];

	int max = 0;

	for (int i = 0; i < child[n].len; i++)
	{
		int temp = (dp[child[n].parents[i]] == -1) ? f(child[n].parents[i], dp, weight, child) : dp[child[n].parents[i]];

		if (temp > max) max = temp;
	}

	dp[n] = max + weight[n];
	return max + weight[n];
}

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

	int result = (int*)calloc(test_case, sizeof(int));
	int result_index = 0;

	for (int ttc = 0; ttc < test_case; ttc++)
	{
		int n, rules;
		scanf("%d %d", &n, &rules);

		for (int i = 0; i < 1001; i++)
		{
			weight[i] = 0;
			dp[i] = -1;
			init_rel(&child[i]);
		}

		for (int i = 0; i < n; i++)
			scanf("%d", &weight[i + 1]);

		for (int i = 0; i < rules; i++)
		{
			int p, c;
			scanf("%d %d", &p, &c);

			child[c].parents[child[c].len++] = p;
		}

		int obj;
		scanf("%d", &obj);

		result[result_index++] = f(obj, dp, weight, child);
	}

	for (int i = 0; i < result_index; i++)
		printf("%d\n", result[i]);

	free(result);
}

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

문제

문제

출처

ICPC

동적계획법 재귀 둘다 시간초과가 떠서 둘이 섞어봤는데도 시간초과가 뜨네요.

mkleeboy3 5년 전 0

mkleeboy3 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말