글 읽기 - 두 함수의 차이점을 모르겠습니다...

temp 7년 전 0

첫번째거가 제 코드인데 계속 오답이 뜨길래 뭘까하면서 게시판을 봤습니다.

그런데 어떤분의 코드가 저와똑같다고 느꼈습니다. 그런데 정답이더군요..

제가 보기엔 둘이 완전 똑같은 알고리즘같은데 왜 저는 틀리고 저분은 맞았을까요?

어떤 차이가 있는걸까요?

다른 부분은 차이가 없습니다. 함수만 바꿔서 해보니 정답이 뜨더라구요...

//제가 작성한 코드 오답이 나왔습니다.
int dfs(int now)
{
	int val[2] = { 0, };
	for (int i = 0; i < v[now].size(); i++)
	{
		int next = v[now][i].first;
		val[i]=dfs(next)+v[now][i].second;
	}
	ans = max(ans, val[0] + val[1]);
	return max(val[0], val[1]);
}

//질문작성게시판에서 어떤분의 정답코드
int solve(int cur) {
	int b1 = 0, b2 = 0;
	for (int i = 0; i<v[cur].size(); ++i) {
		int next = v[cur][i].first, len = v[cur][i].second;
		int cand = solve(next) + len;
		if (cand > b1) { b2 = b1; b1 = cand; }
		else if (cand > b2) { b2 = cand; }
	}
	ans = max(ans, b1 + b2);
	return b1;
}

yukariko 7년 전 2

트리 노드의 자식의 개수는 항상2개가 아니라 더 많을 수 있습니다.

따라서 val[i] 에서 오버플로우가 발생할 수 있습니다.

temp 7년 전 0

그럼 정답코드에서 b1과 b2로 정의하고 ans에 두개의 합을 처리한부분은

자식노드가 더 많다면 저부분역시 틀려야 하지 않나요?

yukariko 7년 전 2

정답코드는 여러개의 자식중 가장큰 2개만을 고르는 과정이 담겨있습니다.

자식노드가 많아도 필요한건 가장 긴 2개가 필요하기때문에

문제없는코드로 보입니다.

temp 7년 전 0

아..지름이라는 사실을 잊고있었네요...

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

문제

문제

출처

ICPC

두 함수의 차이점을 모르겠습니다...

temp 7년 전 0

yukariko 7년 전 2

temp 7년 전 0

yukariko 7년 전 2

temp 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말