글 읽기 - [16235 나무재테크] 최대한 줄인거 같은데.. 시간초과가 계속 나네요..

mycool0905 4년 전 0

보니까 봄이랑 가을 과정은 합쳐도 될 것 같아서 합쳐서 하고,

각 지역별로 vector 만드는 거랑 일차원으로 vector 만드는 게 별 차이가 없을 것 같아서

이렇게 했는데.. 시간초과가 계속 나네요.. 많은 조언 부탁드립니다.

#include <iostream>
#include <vector>

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

typedef struct tree {
	int x;
	int y;
	int age;
}tree;

using namespace std;

int map[10][10];
int A[10][10];
int N, M, K;
vector<tree> aliveTrees;
vector<tree> deadTrees;

bool isIn(int x, int y) {
	if (0 <= x && x < N && 0 <= y && y < N)
		return true;
	else
		return false;
}

void springAndFall() {
	int newX, newY;
	for (unsigned int i = 0; i < aliveTrees.size(); i++) {
		if (aliveTrees[i].age <= map[aliveTrees[i].x][aliveTrees[i].y]) {
			map[aliveTrees[i].x][aliveTrees[i].y] -= aliveTrees[i].age;
			aliveTrees[i].age++;

			if (aliveTrees[i].age % 5 == 0) {
				for (int j = 0; j < 8; j++) {
					newX = aliveTrees[i].x + dx[j];
					newY = aliveTrees[i].y + dy[j];
					if (isIn(newX, newY)) {
						aliveTrees.insert(aliveTrees.begin(), { newX,newY,1 });
						i++;
					}
				}
			}
		}
		else {
			deadTrees.push_back({ aliveTrees[i].x,aliveTrees[i].y,aliveTrees[i].age });
			aliveTrees.erase(aliveTrees.begin() + i--);
		}
	}
}

void summer() {
	for (auto i : deadTrees) {
		map[i.x][i.y] += i.age / 2;
	}
	deadTrees.clear();
}

void winter() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] += A[i][j];
		}
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int x, y, age;

	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> A[i][j];
			map[i][j] = 5;
		}
	}

	for (int i = 0; i < M; i++) {
		cin >> x >> y >> age;
		aliveTrees.push_back({ x - 1,y - 1,age });
	}

	for (int k = 0; k < K; k++) {
		springAndFall();
		summer();
		winter();
	}

	cout << aliveTrees.size() << "\n";

	return 0;
}

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

문제

문제

출처

ICPC

[16235 나무재테크] 최대한 줄인거 같은데.. 시간초과가 계속 나네요..

mycool0905 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말