글 읽기 - 도와주세요

shinhj88 8년 전 0

DFS로 순회하면서 얼리어답터인경우 다음 노드에는 얼리어답터가 아닌경우로 나누어서 메모라이즈하여 답을 구했는데 계속 오답으로 나옵니다.

틀린부분좀 고쳐주세요

/*
 * 2533.cpp

 *
 *  Created on: 2016. 1. 21.
 *      Author: shinheejoon
 */
#include <vector>
#include <memory.h>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
vector<int> G[1000001];
int DT[1000001][2];
bool check[1000001];
int memo(int u,int install)
{
	int& ret = DT[u][install];
	if(ret != -1)return ret;
	check[u] = true;
	if(install) ret=1;
	else ret = 0;

	for(int i = 0;i <G[u].size(); i++){
		int v = G[u][i];
		if(!check[v])ret += memo(v,!install);
	}
	check[u] = false;
	return ret;
}
int main()
{
	memset(DT,-1,sizeof(DT));
	memset(check,0,sizeof(check));
	scanf("%d",&n);
	for(int i = 0; i < n - 1; i++){

		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	printf("%d\n",min(memo(1,0),memo(1,1)));


	return 0;
}

yukariko 8년 전 1

자신의 노드가 얼리어답터라고 해도, 다음 노드가 항상 얼리어답터가 아닌것은 아닙니다.

shinhj88 8년 전 0

@yukariko님 감사 합니다.

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

문제

문제

출처

ICPC

도와주세요

shinhj88 8년 전 0

yukariko 8년 전 1

shinhj88 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말