글 읽기 - 총체적 난국입니다....

changu02 7년 전 0

이제막 알고리즘 공부를 시작한 3학년 학부생입니다.

시간복잡도와 공간복잡도를 많이 고려하지 않고 알고리즘을 짜다보니 이렇게 시간초과가 나타나게 되었습니다.

dfs 재귀방법을 사용하였구요. 여러배열들을 동적할당 해주었는데, 어디서 시간초과가 나타나는지 모르겠습니다.

질문게시판에 올라온 모든 testcase는 완벽하게 수행됩니다. 어디에서 시간을 날렸는지 알려주실수 있으신지요

#include <iostream>
#include <fstream>
#define Max(a,b) ((a)>(b) ? (a):(b))
using namespace std;
int maxOfPath = 0;
void pathfinder(int whatToMake, int numOfBuild, int **button, int wholeSum, int *needTime,int numOfRule, int *alreadyPassedFlag);
int main()
{
	int numoftestcase;
	cin >> numoftestcase;
	for (int i = 0; i < numoftestcase; i++)
	{
		int numOfBuild, numOfRule;
		cin >> numOfBuild >> numOfRule;
		int** button = new int*[Max(numOfBuild, numOfRule)];
		for (int j = 0; j < Max(numOfBuild, numOfRule); j++)
		{
			button[j] = new int[Max(numOfBuild, numOfRule)];
			for (int k = 0; k < Max(numOfBuild, numOfRule); k++)//0으로 초기화
			{
				button[j][k] = 0;
			}
		}
		int *needTime = new int[Max(numOfBuild, numOfRule)];
		for (int j = 0; j < numOfBuild; j++)//j+1 번 건물짓는데 걸리는시간
		{
			cin >> needTime[j];
		}
		int *alreadyPassedFlag = new int[Max(numOfBuild, numOfRule)];
		for (int j = 0; j < Max(numOfBuild, numOfRule); j++)//시작점이 여러개일때 시작점마다의 max time 을 저장해둠
		{
			alreadyPassedFlag[j] = 0;
		}
		for (int j = 0; j < numOfRule; j++)//button[도착점][시작점] ==0 이면 연결안되있고 1이면 연결되있단소리
		{
			int temp;
			cin >> temp;
			int bHole;
			cin >> bHole;
			button[bHole - 1][temp-1] = 1;
		}
		int whatToMake = 0;
		cin >> whatToMake; //무엇이 만들어지면 완성되는지
		pathfinder(whatToMake-1,numOfBuild,button,0, needTime, numOfRule, alreadyPassedFlag);
		for (int i = 0; i < Max(numOfBuild, numOfRule); i++)
		{
			maxOfPath = Max(maxOfPath, alreadyPassedFlag[i]);
		}
		cout << maxOfPath << '\n';
		maxOfPath = 0;
		delete[]needTime;
		delete[]button;
		delete[]alreadyPassedFlag;
	}
	return 0;
}
void pathfinder(int whatToMake,int numOfBuild,int **button,int wholeSum,int *needTime,int numOfRule, int *alreadyPassedFlag)
{
		int k = 0;
		int h = 0;
		while (h < Max(numOfBuild, numOfRule))//시작점인지 조사
		{
			if (button[whatToMake][h] == 0) //button[도착점][시작점] ==0 이면 연결안되있고 1이면 연결되있단소리
			{
				k++;
			}
			h++;
		}
		if (k == Max(numOfBuild, numOfRule))//시작점일때
		{
			maxOfPath = Max(maxOfPath, wholeSum + needTime[whatToMake]);
			return;
		}
	
	for (int i=0; i < Max(numOfBuild, numOfRule);i++)
	{
		if (button[whatToMake][i] == 1)
		{
			pathfinder(i, numOfBuild, button, wholeSum + needTime[whatToMake],needTime, numOfRule,  alreadyPassedFlag);
		}
	}
}

amugeona 7년 전 0

해당 소스는 올바르게 돌지만, 빠른 시간안에 돌지 않는다는 의미로 해석됩니다.

먼저 문제의 자료들을 저장할 배열을 정의합니다.

C[n] : n번째 건물이 지어지는 시간

P[n][m] : n번째 건물을 짓기 전에 m번째 건물을 지을 수 없는지의 여부(없으면 1, 있으면 0)

배열이 정의되었을 때, 하나의 함수를 정의해서 고민을 해봅시다.

F(n) : n번째 건물을 지을 수 있게 되는 최소 시간

우리가 구하려는 답은 F(w)가 되겠습니다.

F(n)은 다음과 같이 구할 수 있습니다.

F(n) = max( F[ i ] + C[ i ] ( i : P[ i ][ n ] 가 1을 만족하는 건물의 번호 )

그런데 F(n)은 정의에 의해서 한번 계산이 완료되면 "다시 구할 필요가 없는" 함수입니다.

따라서 이 부분을 "메모이제이션 기법"을 사용하시면 시간 내에 해결이 가능해지게 됩니다.

궁금하신 점이 있으시면 답변 달아주세요.

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

문제

문제

출처

ICPC

총체적 난국입니다....

changu02 7년 전 0

amugeona 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말