글 읽기 - 1005번 ACM Craft 런타임 에러

fineman91 8년 전 0

각 건물을 노드로 생각하고

adjacency matrix를 만들었습니다.

그리고 각 건물에서 최대 비용(시간)이 걸리는 건물로 이동하면서 total cost를 구하는 알고리즘입니다.

근데 런타임 에러가 뜹니다. 문제가 무엇일까요.. 특이한 테스트 케이스가 있을까요?

#include <iostream>

int calcMaxCost(const int numOfBuilding, const int numOfBuildOrder, const int end, int **adjacency, int buildCost[]);

int main()
{
	int T = 0;
	std::cin >> T;

	for (int testcase = 0; testcase < T; ++testcase)
	{
		int n = 0, k = 0;
		std::cin >> n >> k;

		int **adjacency = new int*[n-1];
		for (int i = 0; i < n-1; ++i)
			adjacency[i] = new int[n];

		for (int i = 0; i < n-1; ++i)
			for (int j = 0; j < n; ++j)
				adjacency[i][j] = -1;

		int *buildCost = new int[n];
		for (int i = 0; i < n; ++i)
			std::cin >> buildCost[i];

		for (int i = 0; i < k; ++i)
		{
			int x = 0, y = 0;
			std::cin >> x >> y;

			adjacency[x - 1][y - 1] = buildCost[y - 1];
		}

		int end = -1;
		std::cin >> end;

		std::cout << calcMaxCost(n, k, end, adjacency, buildCost) << std::endl;

		delete[] buildCost;
		for (int i = 0; i < n-1; ++i)
			delete[] adjacency[i];
		delete[] adjacency;
	}
	return 0;
}

int calcMaxCost(const int numOfBuilding, const int numOfBuildOrder, const int end, int **adjacency, int buildCost[])
{
	int totalCost = buildCost[0];
	int tempCost = 0, next = -1;

	for (int i = 0; i < end - 1;)
	{
		tempCost = 0;
		for (int j = i + 1; j < numOfBuilding; ++j)
		{
			if (adjacency[i][j] != -1 && tempCost < adjacency[i][j])
			{
				tempCost = adjacency[i][j];
				next = j;
			}
		}
		i = next;
		totalCost += tempCost;
	}
	return totalCost;
}

yukariko 8년 전 0

재귀함수의 다중 호출로 인해 스택메모리가 초과되어 런타임에러가 발생하는게 아닌가 싶습니다.

아마 런타임에러가 고쳐지면 시간초과를 받을듯한데요,

DP를 이용하면 중복되는 호출을 줄이면서 빠르게 문제를 해결할 수 있습니다.

fineman91 8년 전 0

재귀함수를 사용하지는 않았습니다만.. 왜 런타임에러가 뜨는지 모르겠네요..ㅠㅠ

yukariko 8년 전 0

어 그러네요

그냥 배열선언에 n-1을 n으로 고쳐보니 시간초과가 뜨네요.

아마 x,y 를 adj 배열에 넣을때 x가 n-1을 벗어날 수 있지않을까 싶습니다.

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

문제

문제

출처

ICPC

1005번 ACM Craft 런타임 에러

fineman91 8년 전 0

yukariko 8년 전 0

fineman91 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말