글 읽기 - 1005번 60퍼 에서 시간초과가 계속 떠요

river97 6년 전 0

짜고 올려봤는데 시간초과가 뜨네요.. 다르분들 질문도 뫘지만 이유를 잘 모르겟어요 동적프로그래밍 싸도 시간초과가 뜨는데 왜이런걸까요ㅠ?

#include <stdio.h>
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))  
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))  

int T, j, n,output;
int count = 0;
int bn, br, bt[1001];
int BuildR1, BuildR2, BuildL;
int map[1001][1001];
int dp[1001];
int match(int n);

int main() {

	scanf("%d", &T);


	for (int i = 0; i < T; i++)
	{
		scanf("%d %d", &bn, &br);
		for (int q  = 0; q < 1001; q++)
		{
			dp[q] = bt[q] = 0;
		}
		for (j = 1; j <= bn; j++)
			scanf("%d", &bt[j]);
	
		for (int p= 0; p < 1001; p++) {

			for (int l = 0; l< 1001; l++)
				map[p][l] = 0;
		}
		for (int k = 1; k <= br; k++)
		{
			scanf("%d %d", &BuildR1, &BuildR2);
			map[BuildR2][BuildR1] = 1;
		}

		scanf("%d", &BuildL);
		output = match(BuildL);

		printf("%d\n", output);
	}
	return 0;
}

int match(int n)
{
	if (dp[n] > 0)
		return dp[n];
	int max = 0;
	for (int q  = 1; q <= bn; q++)
	{
		if (map[n][q] == 1)
			max = MAX(max, match(q));
	}


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

jh05013 6년 전 0

https://www.acmicpc.net/board/...
"질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요."

jh05013 6년 전 0

그리고 문제 번호를 적는 칸이 있습니다.

leejk9592 6년 전 2

N이 1000, K가 100000 일 때, bt[:]에 모든 값이 0이면 다이나믹 프로그래밍 방식이 작동하지 않고
모든 경우의 수를 탐색하게 되서 시간초과가 발생하시는 걸 껍니다.

제가 제안하는 방식은 dp 배열을 -1로 초기화 하고, match 함수에서 dp[n] > -1 일 때 return
아니면 dp[n] = 0으로 초기화하고 dfs 하는 방식으로 하심이...

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

문제

문제

출처

ICPC

1005번 60퍼 에서 시간초과가 계속 떠요

river97 6년 전 0

jh05013 6년 전 0

jh05013 6년 전 0

leejk9592 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말