글 읽기 - 우수마을.. 트리 dp 연산횟수에 관해서 질문드립니다.

jangzzang 4년 전 0

아래 코드로 AC 를 받기는 했는데 항상 이런 다이나믹 류의 문제를 풀때 시간복잡도에 대해서 감이 안잡히네요.

DFS함수를 돌면서 문제조건에 맞춰서 요구하는대로 우수마을일때, 아닐때를 나누면서 재귀호출을 했는데 , 혹시 이런 류의 문제들은 연산 횟수계산을

어떤식으로 해야할 지 알려주실 수 있으신가요 ㅠㅠㅠ

N이 만까지 가는 범위인데도 아래의 방식이 20ms밖에 안나오는 것도 잘 이해가 되지 않습니다 함수안에서 두가지의 경우로 제곱의 형태로 호출이 되는데 그냥 덧셈의 느낌으로 시간이 증가하는 것 같더라구요...

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
int parent[10010];
int cost[10010];
int n,root;
bool vtd[10010];
vector<int> v[10010];
vector<int> vv[10010];
queue<int> q;
int dfs(int node,int isGood);
void bfs();
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cost[i]);
	}
	for (int i = 1; i <= n - 1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vv[x].push_back(y);
		vv[y].push_back(x);
	}

	root = 1;
	bfs();

	int ans = max(dfs(root, 0), dfs(root, 1));
	printf("%d", ans);
}
void bfs() {
	q.push(1);
	vtd[1] = true;

	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int i = 0; i < vv[node].size(); i++) {
			int nextNode = vv[node][i];
			if (!vtd[nextNode]) {
				vtd[nextNode] = true;
				v[node].push_back(nextNode);
				q.push(nextNode);
			}
		}
	}
}

int dfs(int node,int isGood) {
	if (v[node].size() == 0) {
		if (isGood)return cost[node];
		else return 0;
	}

	int result = 0;
	if (isGood) {
		int tmp = 0;
		for (int i = 0; i < v[node].size(); i++) {
			 tmp += max(result, dfs(v[node][i], 0));
		}
		result = tmp;
	}
	else {
		int tmp = 0;
		for (int i = 0; i < v[node].size(); i++) {
			tmp += max(dfs(v[node][i], 1),dfs(v[node][i], 0));
		}
		result= tmp;
	}
	if (isGood)
		return result + cost[node];
	else
		return result;
}

sait2000 4년 전 1

메모이제이션이 없어서 지수 시간 맞아요 테스트케이스가 약해요 추가요청 하고 올게요

만약에 메모이제이션, 즉 각 함수 호출에 대해 결과를 리턴하기 전에 저장을 해두고 다음 호출 때 결과가 저장이 되어있으면 추가적인 함수호출을 하지 않고 바로 값을 돌려준다고 치면 값이 저장이 안 되어있어서 값을 계산해야만 하는 상황은 최대 (노드 수) * 2 (isGood이 0아니면 1이니까 2)번이 되고, 그러면 dfs호출은 아무리 많아봤자 그거의 (대략) 2배가 될 테고. 각 호출에서 자식 노드에 대한 시간을 뺀 시간도 최대 노드 수에 비례할 테니까 O(n)이 되죠.

jangzzang 4년 전 0

넵 감사합니다. 원래는 시간초과가 나야하는게 맞는 거였군요 그럼.

memo 이차원 배열 하나 추가해서 메모이제이션하니까 4ms까지 주네요

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

문제

문제

출처

ICPC

우수마을.. 트리 dp 연산횟수에 관해서 질문드립니다.

jangzzang 4년 전 0

sait2000 4년 전 1

jangzzang 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말