글 읽기 - C++ 나무재테크 문제 질문입니다..

lllllllhisll 4년 전 0

시간초과가 저명하긴하지만 문제 답이라도 나오고 싶은데 반례라고 보여진 것에서 틀린답이나옵니다....

디버깅만 5시간째 하고있는데 너무 답답해서 질문드립니다..ㅠㅠ

로직상 잘못된 부분이 있는지 지적해주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <queue>
#include <functional>
using namespace std;

int N, M, K;
int maps[10][10];		//현재 양분량
int food[10][10];		//추가될 양분
int num = 0;
int tree_num;		//나무 갯수
int row[8] = { -1,-1,-1,0,1,1,1,0 };
int col[8] = { -1,0,1,1,1,0,-1,-1 };
priority_queue<int, vector<int>, greater<int>> tree[10][10];		//나이 좌표
int treeIs[10][10];		//각 칸에 존재하는 나무 갯수

void year()		//한해동안 나무들 재테크 구현,  각 계절은 나무 갯수만큼 진행
{
	/*봄, 여름*/
	/*나무가 있는 칸에 나이만큼 양분 먹임*/
	/*1살 추가*/
	/*양분 못먹는 나무는 나이/2만큼 해당 칸에 양분 추가*/
	/*여러나무가 있을 수 있으니 각 나무들을 인덱스로 접근*/

	queue<int> temp;		//한칸에서 각 살아있는 나무들의 나이집합
							/*각 칸 검사*/
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			/*나무가 없는 곳은 조사를 하지 않는다.*/

			if (treeIs[i][j] == 0) continue;
			int tmp_age = 0;		//죽은 나무들의 나이/2의 합, 여름에 양분추가를 위해 사용
									/*한 칸에 들어있는 나무들을 temp에 삽입*/
			for (int z = 0; z < treeIs[i][j]; z++)
			{
				temp.push(tree[i][j].top());
				tree[i][j].pop();
			}
			/*각 칸의 나무 숫자만큼 양분 흡수 진행*/
			int siz = treeIs[i][j];
			for (int z = 0; z < siz; z++)
			{
				/*양분 흡수*/
				maps[i][j] -= temp.front();
				/*양분이 나이보다 작은 경우 양분이 음수가 되는 경우이다.*/
				/*이 때 해당 나무 이후의 나무들은 죽으면서 나이/2만큼의 양분을 남겨준다.*/
				if (maps[i][j] < 0)
				{
					/*죽은 나무 갯수만큼 treeIs값 감소*/
					treeIs[i][j] -= temp.size();
					maps[i][j] += temp.front();
					/*양분이 부족한 나무들이므로 죽으면서 양분을 남김*/
					for (int t = 0; t < temp.size(); t++)
					{
						tmp_age += temp.front() / 2;
						temp.pop();
					}
					/*해당 칸의 코드 종료*/
					maps[i][j] += tmp_age;
					break;
				}
				/*정상적으로 양분을 먹은 나무들은 한 살 추가하여 다시 tree에 저장*/
				tree[i][j].push(temp.front() + 1);
				temp.pop();
			}
		}
	}

	queue<int> temp2;
	/*가을*/
	/*번식기, 나이가 5의 배수인 나무들은 8방향으로 번식*/
	/*모든 방향을 확인하며 5의 배수인 나무 주위에 나이가 1인 나무 추가*/
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (treeIs[i][j] == 0) continue;

			/*각 칸의 나무들을 temp에 삽입*/
			for (int z = 0; z < treeIs[i][j]; z++)
			{
				temp2.push(tree[i][j].top());
				tree[i][j].pop();
			}

			/*만약 temp에 들어있는 나무들의 나이가 5의배수이면*/
			/*해당 칸을 기준으로 8방향으로 나무들 생성*/
			int siz = temp2.size();

			for (int z = 0; z < siz; z++)
			{
				if ((temp2.front() % 5) == 0)
				{
					for (int d = 0; d < 8; d++)
					{
						int nr = i + row[d];
						int nc = j + col[d];

						/*유효한 좌표인 경우*/
						/*1의 나이를 갖는 나무 추가*/
						/*해당 칸에 나무갯수 추가*/
						if (nr >= 0 && nc >= 0 && nr < N && nc < N)
						{
							treeIs[nr][nc]++;
							tree[nr][nc].push(1);
						}
					}
				}
				tree[i][j].push(temp2.front());
				temp2.pop();
			}
		}
	}
	
	/*겨울*/
	/*양분 추가*/
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			maps[i][j] += food[i][j];
		}
	}
	/*cout << "\n";
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << maps[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << tree[i][j].size() << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> K;
	tree_num = M;

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

	for (int i = 0; i < M; i++)
	{
		int age, x, y;
		cin >> x >> y >> age;
		tree[x - 1][y - 1].push(age);
		treeIs[x - 1][y - 1] = 1;
	}

	for (int i = 0; i < K; i++)
		year();

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			num += treeIs[i][j];
		}
	}

	cout << num << "\n";

	return 0;
}

seico75 4년 전 0

입력에서 x 는 r 이고 y는 c입니다.

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

문제

문제

출처

ICPC

C++ 나무재테크 문제 질문입니다..

lllllllhisll 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말