글 읽기 - 시간초과 해결방법이 있을까요

dongmin12 5년 전 0

priority queue 말고 벡터와 erase를 사용해서 구현했었는데
똑같이 시간초과가 나더라구요
코드 내에서 시간을 줄일수 있는 부분 알려주시면 감사하겠습니당

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include<cstring>
using namespace std;

int N, M, K;
int A[11][11]; // 각 위치 나무의 나이
int INPUT_A[11][11]; // 각 위치 나무의 나이
int AR[8] = { 0,0,1,1,1,-1,-1,-1 };
int BR[8] = { 1,-1,1,0,-1,0,1,-1 };
priority_queue <pair< int, pair< int, int> > > age;   // -나이, (x,y)위치
priority_queue <pair< int, pair< int, int> > > age_c; // 카피
priority_queue <pair< int, pair< int, int> > > age2;  // 죽은 나무

void INPUT()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> INPUT_A[i][j];
			A[i][j] = 5;
		}
	}
	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		age.push(make_pair(-z, make_pair(x, y)));
	}
}
void spring()
{
	//2. 봄에 자신의 나이만큼 양분을 먹음  & 먹으면 나이가 1 증가
	//3. 나이가 어린 나무부터 양분을 먹음. & 먹지못한 나무는 죽음
	int s = age.size();
	for (int i = 0; i < s; i++)
	{
		int a = -age.top().first;
		int x = age.top().second.first;
		int y = age.top().second.second;
		age.pop();

		if (A[x][y] >= a) // 양분이 충분하면  
		{
			A[x][y] -= a;
			age_c.push(make_pair(-(a+1), make_pair(x, y)));
		}
		else // 모자르면 죽음..
		{
			age2.push(make_pair(-(a/2), make_pair(x, y)));
		}
	}

	while (!age_c.empty())
	{
		age.push(age_c.top());
		age_c.pop();
	}
}
void summer()
{
	//4. 여름에는 죽은 나무가 양분으로 변함.  
	int s = age2.size();
	for (int i = 0; i < s; i++)
	{
		int a = -age2.top().first;
		int x = age2.top().second.first;
		int y = age2.top().second.second;
		age2.pop();
		A[x][y] += a;
	}
}
void fall()
{
	//5. 가을엔 나이 5배수의 나무가 번식(인접 8칸)
	int s = age.size();
	for (int i = 0; i < s; i++)
	{
		int a = -age.top().first;
		int x = age.top().second.first;
		int y = age.top().second.second;
		age.pop();
		age_c.push(make_pair(-a, make_pair(x, y)));
		if (a%5 == 0) // 나무의 나이가 5의 배수면
		{
			for (int i = 0; i < 8; i++)
			{
				int X = AR[i] + x;
				int Y = BR[i] + y;
				if (0 < X && X <= N && 0 < Y && Y <= N)
				{
					age_c.push(make_pair(-1, make_pair(X, Y)));
				}
			}
		}
	}
	while (!age_c.empty())
	{
		age.push(age_c.top());
		age_c.pop();
	}
}
void winter()
{
	//6. 겨울엔 로봇이 양분을 추가함.각 칸에 추가되는 양분은 A[r][c]이고 입력으로 주어짐.
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			A[i][j] += INPUT_A[i][j];
		}
	}
}
int main(void)
{
	INPUT();
	

	//7. K년 후의 살아있는 나무의 개수

	for (int i = 0; i < K; i++)
	{
		spring();
		summer();
		fall();
		winter();
		if (age.size() == 0)
			break;
	}

	cout << age.size() << endl;
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 해결방법이 있을까요

dongmin12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말