글 읽기 - 시간초과가 왜뜨는걸까요?

tkqlzz 7년 전 0

런타임 에러부터해서 메모리초과 까지 거쳐 시간초과에서 막히네요.

시간초과때문에 cin cout을 scanf printf 로 고쳤고 다른 부분도 나름 개선했는데

제 지식으로는 뭐가문제인지 잘모르겠네요 혹시나 뭐가문제인지 보이시면 조언좀 부탁드립니다.

#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

void search(int num);
int B[1001];
int maxVal;
int sum;
vector<vector<int> > arr;

int main() {
	int T;
	int i, Goal, N, K, x, y;
	scanf("%d", &T);
	while (T--) {
		maxVal = 0, sum = 0;
		memset(B, 0, sizeof(B));

		// N : 건물 갯수 K : 건설순서규칙 개수 입력
		scanf("%d%d", &N, &K);

		arr = vector<vector<int> >(N + 1);

		// 건물당 건설시간 입력
		for (i = 1; i < N + 1; i++) {
			scanf("%d", &B[i]);
		}
		
		// 건설순서 입력
		for (i = 0; i < K; i++) {
			scanf("%d%d", &x, &y);
			arr[y].push_back(x); // y에서 x로 갈수있는 값들 push
		}
		
		// 목표 입력
		scanf("%d", &Goal);		
		search(Goal);
		printf("%d\n", maxVal);
	}
}
void search(int num) {
	int i;

	if (num == 1) {
		sum += B[num];
		if (maxVal < sum)
			maxVal = sum;
		sum -= B[num];
		return;
	}

	for (i = 0; i < arr[num].size(); i++) {
		sum += B[num];
		search(arr[num][i]);
		sum -= B[num];
	}
}

tkqlzz 7년 전 0

아 시작점부터 종점까지 도달하는 경우의수를 모두구해 합을비교하는것보다 하나의 이동거리만큼 비교해가는 구조로 다시 짜니까 되네요

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

문제

문제

출처

ICPC

시간초과가 왜뜨는걸까요?

tkqlzz 7년 전 0

tkqlzz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말