글 읽기 - 시간 초과 질문드립니다. 시간을 줄일 만한 방법이 있을까요?

park780172 3년 전 1

일단 예제 모두 맞게 뜹니다.

여하튼, sort()를 사용하지 않는데도 불구하고 '시간 초과'가 떠서 질문해봅니다.

코드의 어느 부분에서 어떻게 해야 더 줄일 수 있을까요?

계속 고민해봐도 방법이 떠오르지 않아 질문 해봅니다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>

using namespace std;

typedef struct information
{
	int nourishment; // 양분
	int add; // S2D2가 추가해줄 양분
}information;

typedef struct Tree
{
	int age; // 나이
	bool live; // 살아있는지(true), 죽었는지(false) 여부
}Tree;

information Map[101][101]; // 땅

vector<Tree> tree[101][101]; // 나무

void init() // Map(땅) 초기화 작업
{
	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++)
		{
			Map[i][j].nourishment = 0;
			Map[i][j].add = 0;
		}
	}
}

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

int N = 0, M = 0, K = 0;

void simulation()
{
	while (K--) // K년 동안 진행한다.
	{
		// 봄
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				int vSize = tree[i][j].size();
				// (i, j) 칸에 있는 나무 그루를 받는다. 죽어있는 나무, 살아있는 나무 모두 포함이다.

				for (int s = 0; s < vSize; s++) // 그 그루 만큼 for문을 돈다.
				{
					if (!tree[i][j].at(s).live) continue;
					// 죽어있으면, 당연히 무시한다.

					if (Map[i][j].nourishment >= tree[i][j].at(s).age)
					{
						// 양분보다 나이가 더 적다면, 당연히 그 나무가 양분을 자신(나무)의 나이만큼 먹을 수 있다.

						Map[i][j].nourishment -= tree[i][j].at(s).age; // 양분에서 자신(나무)의 나이 만큼 먹는다.
						++tree[i][j].at(s).age; // 자신(나무)의 나이 만큼 양분을 먹었으니 나이가 1살 증가한다.
					}
					else
					{
						// 자신(나무)의 나이가 더 많다면, 죽는다.(=false)
						tree[i][j].at(s).live = false;
					}
				}
			}
		}

		// 여름
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				int vSize = tree[i][j].size();
				// (i, j) 칸에 있는 나무 그루를 받는다. 죽어있는 나무, 살아있는 나무 모두 포함이다.

				for (int s = 0; s < vSize; s++)
				{
					// 죽은 나무라면
					if (!tree[i][j].at(s).live)
					{
						// 그 죽은 나무의 나이의 1/2만큼 그 나무가 마지막까지 있던 칸에 양분을 더해준다.
						Map[i][j].nourishment += tree[i][j].at(s).age / 2;
					}
				}
			}
		}

		// 가을
		Tree T;
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				int vSize = tree[i][j].size();
				// (i, j) 칸에 있는 나무 그루를 받는다. 죽어있는 나무, 살아있는 나무 모두 포함이다.

				for (int s = 0; s < vSize; s++)
				{
					if (!tree[i][j].at(s).live || tree[i][j].at(s).age % 5 != 0) continue;
					// 죽었거나 또는 나이가 5의 배수가 아니라면 무시한다.

					for (int k = 0; k < 8; k++)
					{
						int y = i + dy[k];
						int x = j + dx[k];

						if (y <= 0 || y > N || x <= 0 || x > N) continue;
						// 당연히 범위를 벗어나면, 무시한다.
						// 1 이상 ~ N 이하

						T.age = 1;
						T.live = true;

						tree[y][x].insert(tree[y][x].begin(), T);
						// 제일 첫 위치에 삽입, 어차피 나이는 1이다.
						// 입력으로 주어지는 나무의 위치는 모두 다르기 때문인 것도 있다.
					}
				}
			}
		}

		// 겨울
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				Map[i][j].nourishment += Map[i][j].add;
				// 겨울에는 S2D2가 땅을 돌아다니면서, 땅에 양분을 추가한다.
			}
		}
	}
}

int liveCount()
{
	int ret = 0;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int vSize = tree[i][j].size();

			for (int s = 0; s < vSize; s++)
			{
				// 살아있는 나무를 센다.
				if (tree[i][j].at(s).live) ++ret;
			}
		}
	}

	return ret;
}

int main(void)
{
	init();

	Tree T;

	scanf("%d %d %d", &N, &M, &K);

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			scanf("%d", &Map[i][j].add);
			// S2D2가 추가해줄 양분(=add)를 입력한다.

			Map[i][j].nourishment = 5;
			// 초깃값(초기 양분)은 5이다.
		}
	}

	int x = 0, y = 0, n = 0;

	for (int i = 1; i <= M; i++)
	{
		scanf("%d %d %d", &x, &y, &n);

		T.age = n;
		T.live = true;

		tree[x][y].push_back(T); // [행][열]
	}

	simulation();

	printf("%d\n", liveCount());

	return 0;
}

park780172 3년 전 2

답변 감사합니다.

다른 방법으로 해결하였으나(죽은 나무를 erase), 더 찾아보겠습니다!

감사합니다.

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

문제

문제

출처

ICPC

시간 초과 질문드립니다. 시간을 줄일 만한 방법이 있을까요?

park780172 3년 전 1

park780172 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말