글 읽기 - 1949번 문제에 대한 반례가 어떤것이 있는지 질문 드립니다.

pouminii 6년 전 0

구조체 포인터를 이용하여 노드를 생성하고 이진 트리에 삽입했습니다.

n번째 마을이 우수마을인 경우와 아닌 경우의 2가지 동적계획법을 이용하였고 최종 결과값은 이진트리의 루트노드에 할당이 됩니다 .

반례를 계속 찾아봤으나 답이 안나와서 글 올려봅니다.

이진트리가 아닌 경우에 대한 반례 때문에 틀린 것일까요?

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct Node
{
	int village_num; //마을 번호
	int citizen_count; //마을 주민 수
	Node* leftNode;
	Node* rightNode;
}Node;

int sum(Node* rootNode, bool checkSum);

int dp_true[10000] = { 0, };
int dp_false[10000] = { 0, };

int main(void)
{
	int n;
	cin >> n;
	Node** node = new Node*[n];

	for (int i = 0; i < n; i++) //노드 객체 생성
	{
		int a;
		cin >> a;
		node[i] = new Node{ i, a, NULL, NULL };
	}
	for (int i = 0; i < n-1; i++) //트리에 노드 삽입
	{
		int a, b;
		cin >> a >> b;
		
		if (a < b) //a가 b의 부모노드
		{
			if (node[a-1]->leftNode != NULL)
				node[a-1]->rightNode = node[b-1]; //오른쪽 자식노드에 삽입
			else
				node[a-1]->leftNode = node[b-1]; //왼쪽 자식노드에 삽입
		}
		else //b가 a의 부모노드
		{
			if (node[b-1]->leftNode != NULL)
				node[b-1]->rightNode = node[a-1];
			else
				node[b-1]->leftNode = node[a-1];
		}
	}
	
	cout << max(sum(node[0],false),sum(node[0],true)) << endl;

	for (int i = 0; i < n; i++)
	{
		delete node[i];
	}
	delete[] node;
	return 0;
}

int sum(Node* rootNode, bool checkSum)
{
	int b = 0;
	if (rootNode == NULL) return 0;
	int n = rootNode->village_num;
	if (checkSum) //n번째마을이 우수마을로 선정
	{
		if (dp_true[n] > 0) return dp_true[n]; //n번째 우수마을의 최대값이 있다면 그대로 반환

		return dp_true[n] = rootNode->citizen_count + sum(rootNode->leftNode, false) + sum(rootNode->rightNode, false);
	}
	else //n번째마을이 우수마을 선정 안됨, 왼쪽 또는 오른쪽 노드 하나는 우수마을이어야함
	{
		if (dp_false[n] > 0) return dp_false[n]; //n번째 우수마을이 아닌 마을의 최대값이 있다면 그대로 반환

		if (rootNode->leftNode == NULL && rootNode->rightNode != NULL)
		{
			return dp_false[n] = sum(rootNode->rightNode, true); //오른쪽 자식노드가 우수마을
		}
		else if (rootNode->leftNode != NULL && rootNode->rightNode == NULL)
		{
			return dp_false[n] = sum(rootNode->leftNode, true); //왼쪽 자식노드가 우수마을
		}
		else
		{
			b = sum(rootNode->leftNode, false) + sum(rootNode->rightNode, true);
			b = max(b, sum(rootNode->leftNode, true) + sum(rootNode->rightNode, false));
			b = max(b, sum(rootNode->leftNode, true) + sum(rootNode->rightNode, true)); //양쪽 자식노드가 우수마을
			return dp_false[n] = b;
		}
	}
}

jh05013 6년 전 1

이진트리가 아닐 수도 있습니다.

그리고 번호가 작은 노드가 큰 노드의 부모이도록 하신 것 같은데, 이러면 트리가 제대로 만들어지지 않을 수도 있습니다. (1-3 & 2-3)

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

문제

문제

출처

ICPC

1949번 문제에 대한 반례가 어떤것이 있는지 질문 드립니다.

pouminii 6년 전 0

jh05013 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말