글 읽기 - 리스트로 구현 했을 때 시간초과 질문합니다.

icd0422 4년 전 0

안녕하세요

문제 풀이는 이렇습니다. 전체 땅에 대해 2차원 배열로 구성했습니다. 땅의 요소는 에너지(양분) 과 그 땅에 있는 나무들을 list로 구현했습니다.

처음 나무에 대해서만 리스틀 나이 오름차순으로 정렬 하였고 년도가 지나감에 따라 죽은 나무를 list.erase로 처리했고 추가되는 나무에 대해서는

무조건 나이가 1이니까 리스트의 맨앞의 front_push로 처리하였습니다. 그런데 시간초과가 나네요... 계속 생각을 해봤지만 이해가 가지를 않습니다.

다른 분들 풀이를 보니까 그냥 백터로 구현하고 심지어 계속 정렬까지 하는 코드도 맞다고 나오는데 제 풀이는 왜 시간초과가 나오는지를 모르겠습니다...

리스트면 오히려 요소 삭제에 대해서 빠를 텐데요... 정렬도 처음만 해주고 그 뒤로는 안해주는데도요....

답변해주시면 너무 감사하겠습니다..ㅜㅜ

아래는 제 풀이 코드입니다.

#include<iostream>
#include<list>
#include<set>
#include<algorithm>
#include<cstdio>

#define MAX_MAP_SIZE 13 

using namespace std;

struct Tree {
	int age;

	Tree(int age) {
		this->age = age;
	}
};

bool compare(const Tree& t1, const Tree& t2) {
	return t1.age < t2.age;
}

struct Map {
	int energe;
	list<Tree> trees;
};

int map_size, tree_size, passed_year;
int tree_total_cnt;

Map map[MAX_MAP_SIZE][MAX_MAP_SIZE];
int plus_map[MAX_MAP_SIZE][MAX_MAP_SIZE];

set<pair<int, int > > defalut_tree_pos;

void map_init() {
	for (int i = 1; i <= map_size; i++) {
		for (int j = 1; j <= map_size; j++) {
			map[i][j].energe = 5;
		}
	}
}

void first_map_sort() {
	set<pair<int, int > >::iterator it;

	for (it = defalut_tree_pos.begin(); it != defalut_tree_pos.end(); it++) {
		int x = it->first;
		int y = it->second;

		map[x][y].trees.sort(compare);
	}
}

void eat_energe(int x, int y) {
	list<Tree>* trees = &map[x][y].trees;

	list<Tree>::iterator it = trees->begin();

	int energe_sum = 0;

	while (it != trees->end()) {
		int age = it->age;

		if (age <= map[x][y].energe) {
			map[x][y].energe -= age;
			it->age++;
			it++;
		}
		else {//양분이 부족하다면
			it = trees->erase(it);
			tree_total_cnt--;
			energe_sum += (age / 2);
		}
	}

	map[x][y].energe += energe_sum;
}

void spring_and_summer() {
	for (int i = 1; i <= map_size; i++) {
		for (int j = 1; j <= map_size; j++) {
			eat_energe(i, j);
		}
	}
}

int dx[8] = { 0, 0, -1, 1, -1, -1, 1, 1 };
int dy[8] = { -1, 1, 0, 0, -1, 1, -1, 1 };

void born_tree(int x, int y) {
	list<Tree>* trees = &map[x][y].trees;

	list<Tree>::iterator it;

	for (it = trees->begin(); it != trees->end(); it++) {
		if (((it->age) % 5) == 0) {
			for (int i = 0; i < 8; i++) {
				int mx = x + dx[i];
				int my = y + dy[i];

				if (mx <= 0 || mx > map_size || my <= 0 || my > map_size) continue;

				Tree tree(1);
				map[mx][my].trees.push_front(tree);
				tree_total_cnt++;
			}
		}
	}
}

void fall() {
	for (int i = 1; i <= map_size; i++) {
		for (int j = 1; j <= map_size; j++) {
			born_tree(i, j);
		}
	}
}

void winter() {
	for (int i = 1; i <= map_size; i++) {
		for (int j = 1; j <= map_size; j++) {
			map[i][j].energe += plus_map[i][j];
		}
	}
}

int main() {

	//cin >> map_size >> tree_size >> passed_year;
	scanf("%d %d %d", &map_size, &tree_size, &passed_year);

	map_init();

	for (int i = 1; i <= map_size; i++) {
		for (int j = 1; j <= map_size; j++) {
			//cin >> plus_map[i][j];
			scanf("%d", &plus_map[i][j]);
		}
	}

	for (int i = 0; i < tree_size; i++) {
		int x, y, age;
		//cin >> x >> y >> age;
		scanf("%d %d %d", &x, &y, &age);
		Tree tree(age);
		map[x][y].trees.push_front(tree);
		tree_total_cnt++;
		defalut_tree_pos.insert(make_pair(x, y));
	}

	first_map_sort();

	for (int i = 0; i < passed_year; i++) {
		spring_and_summer();
		fall();
		winter();
	}

	//cout << tree_total_cnt;
	printf("%d", tree_total_cnt);

	return 0;
}

zagabi 4년 전 1

이거 그러면 벡터로 구현하면 시간초과가 안났다는 말씀인가요? 다른 부분 로직 문제 없는거 확실한가요?

joonas 4년 전 1

저도 리스트로 구현했는데 맞았으니 문제는 없을 것 같구요.

양분을 먹고 무럭무럭 자라면, 하나의 칸에 여러 개의 나무가 "엄청" 많을 수도 있습니다.

icd0422 4년 전 0

나무의 속성을 age로만 했는데

age 와 cnt로 구조를 바꿔서 푸니까 시간초과가 안나고 해결했습니다.

리스트 벡터 문제가 아니라 제 로직문제 였습니다ㅜ

다들감사합니다~

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

문제

문제

출처

ICPC

리스트로 구현 했을 때 시간초과 질문합니다.

icd0422 4년 전 0

zagabi 4년 전 1

joonas 4년 전 1

icd0422 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말