글 읽기 - 이 문제는 트리로 풀면 못 푸는 문제인가요?

cconny2002 3년 전 0

다들 이 문제 코딩할 때 배열을 많이 쓰시더군요. 그래서 c의 포인터를 이용해 트리를 만들어 풀었는데 시간 초과/메모리 초과 문제가 뜹니다. 트리로는 제한 시간 또는 제한 용량 내에 풀 수 없나요?

++ 코드는 free가 있을 때는 시간 초과, 없을 때는 메모리 초과가 뜹니다. 혹시 코드 내에 문제가 있는걸까요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef struct node {
	char color;
	unsigned int cost;
	struct node* left;
	struct node* right;
} node;


typedef struct headNode {
	struct node* red;
	struct node* green;
	struct node* blue;
} headNode;

unsigned int min(unsigned int, unsigned int);
void postOrder(node*);
void addChild(node*);
void defineHeadNode(headNode*);

unsigned int total = -1;
unsigned int data[1001][3];
short index;

int main() {
	short N = 0;
	scanf("%hd", &N);

	for (short i = 0; i < N; i++) {
		scanf("%u %u %u", &data[i][0], &data[i][1], &data[i][2]);
	}

	headNode* headNode = malloc(sizeof(struct headNode));
	defineHeadNode(headNode);

	postOrder(headNode->red);
	postOrder(headNode->green);
	postOrder(headNode->blue);

	printf("%u", total);
}

unsigned int min(unsigned int a, unsigned int b) {
	return a > b ? b : a;
}

void postOrder(node* treeNode) {
	if (data[++index][0]) {
		addChild(treeNode);
		postOrder(treeNode->left);
		addChild(treeNode);
		postOrder(treeNode->right);
	}
	else total = min(total, treeNode->cost);
	index--;
	free(treeNode->left);
	free(treeNode->right);
}

void addChild(node* parent) {
	node* child = malloc(sizeof(struct node));
	child->left = NULL; child->right = NULL;

	if (!parent->left) {
		switch (parent->color) {
		case 'r':
			child->color = 'g';
			child->cost = data[index][1] + parent->cost;
			break;
		default:
			child->color = 'r';
			child->cost = data[index][0] + parent->cost;
		}
		parent->left = child;
	}
	else if (!parent->right) {
		switch (parent->color) {
		case 'b':
			child->color = 'g';
			child->cost = data[index][1] + parent->cost;
			break;
		default:
			child->color = 'b';
			child->cost = data[index][2] + parent->cost;
		}
		parent->right = child;
	}
}

void defineHeadNode(headNode* h) {
	node* r = malloc(sizeof(struct node));
	node* g = malloc(sizeof(struct node));
	node* b = malloc(sizeof(struct node));

	r->color = 'r'; r->cost = data[0][0];
	g->color = 'g'; g->cost = data[0][1];
	b->color = 'b'; b->cost = data[0][2];

	r->left = NULL; r->right = NULL;
	g->left = NULL; g->right = NULL;
	b->left = NULL; b->right = NULL;

	h->red = r; h->green = g; h->blue = b;
}

sait2000 3년 전 1

이 문제는 모든 경우를 다 해보면서 푸는 문제가 아닙니다. 몇 경우에 대해서 비슷한 계산을 반복하게 되는데, 이런 경우를 한 번만 계산하도록 식을 바꿔서 시간을 줄여야 합니다. 자세한 건 문제 풀이를 검색하거나 동적 계획법(dynamic programming, DP)에 대해 알아보세요.

cconny2002 3년 전 0

DP에 관련된 글을 몇개보니 직관적으로는 이해가 갑니다. 그럼 또 다른 새로운 질문인데, 만약 집으로 칠할 수 있는 색깔이 4개 이상이여도 DP로 풀 수 있나요?

sait2000 3년 전 1

될 거 같네요.

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

문제

문제

출처

ICPC

이 문제는 트리로 풀면 못 푸는 문제인가요?

cconny2002 3년 전 0

sait2000 3년 전 1

cconny2002 3년 전 0

sait2000 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말