글 읽기 - memoization으로 시간 초과는 없앴는데 어디서 틀린 걸까요?

dohyeokkim 8년 전 0

제 방식은 목적지로부터 거꾸로 indegree가 0인 node에 도착할 때까지 DFS를 하는 것입니다.

맨 처음에 시간초과가 떠서 결과 저장해 줬더니 시간 초과는 안 뜨는데 답이 틀리네요.

기본 2개 test case와 다른 질문글에 올라와 있던 19개의 test case도 모두 맞게 뜹니다.

어떤 부분이 틀린 걸까요?

#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

vector<int> costs;
vector<vector<int>> G;
vector<int> memo;
int max_cost;

void dfs(int v, int cur_cost) {
	if (G[v].empty()) {
		max_cost = max(max_cost, cur_cost);
		return;
	}

	if (memo[v] != 0) {
		max_cost = max(max_cost, memo[v] + cur_cost);
		return;
	}

	int max_tmp = -1;
	for (vector<int>::iterator iter = G[v].begin(); iter != G[v].end(); iter++) {
		max_tmp = max(max_tmp, memo[*iter] + costs[*iter]);
		dfs(*iter, cur_cost + costs[*iter]);
	}

	memo[v] = max_tmp;
}

int main() {
	int t, n, k, a, b, aim;

	scanf("%d", &t);
	while (t--) {
		max_cost = 0;
		scanf("%d %d", &n, &k);
		costs.clear();
		costs.resize(n + 1);
		G.clear();
		G.resize(n + 1);
		memo.clear();
		memo.resize(n + 1, 0);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &costs[i]);
		}
		for (int i = 0; i < k; i++) {
			scanf("%d %d", &a, &b);
			G[b].push_back(a);
		}
		scanf("%d", &aim);
		dfs(aim, costs[aim]);
		printf("%d\n", max_cost);
	}
	
	return 0;
}

dohyeokkim 8년 전 0

sh0416님이 local로 해결해주셨습니다.

안되는 이유는 25번째 줄과 26번째 줄의 순서가 바껴서...

dfs 돌고 와야 memo가 update 되어 있을텐데 update 되지 않은 memo를 가지고 또 이용하고 있었네요...

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

문제

문제

출처

ICPC

memoization으로 시간 초과는 없앴는데 어디서 틀린 걸까요?

dohyeokkim 8년 전 0

dohyeokkim 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말