Memo

• 최근에 푼 구현 문제중에서 가장 어려웠습니다.. 체감 난이도 골드 3
• 한 칸에 여러 파이어볼이 존재할 수 있다는 것을 vector로 표현할 수 밖에 없었습니다.(저는)
• 코딩 테스트 한에서 인덱스 규칙을 하나로 통일하는 것은 선택이 아닌 필수라 생각합니다.

Code

제출 날짜

2021/03/23

메모리

4480 KB

시간

100 ms

#include <iostream>
#include <vector>
#include <string.h>
#include <cmath>

int N, M, K;
std::vector<std::vector<std::vector<int> > >magic;
std::vector<std::vector<int> > fireball;
std::vector<std::vector<int> > fireball_tmp;
std::vector<std::pair<int, int> >check;
int visited[53][53];

int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int s_d[4] = {0, 2, 4, 6};
int o_d[4] = {1, 3, 5, 7};

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N >> M >> K;
	fireball.resize(M, std::vector<int>(6));
	for (int i = 0 ; i < M ; i++)
		for (int j = 1 ; j <= 5 ; j++)
			std::cin >> fireball[i][j];
}

void get_magic(int ind, int &r, int &c, int &m, int &s, int &d)
{
	r = fireball[ind][1];
	c = fireball[ind][2];
	m = fireball[ind][3];
	s = fireball[ind][4];
	d = fireball[ind][5];
}

void move_action(int ind, int r, int c, int s, int d)
{
	int l_dx = (s * N + c + dx[d] * s) % N;
	int l_dy = (s * N + r + dy[d] * s) % N;

	r = !l_dy ? N : l_dy;
	c = !l_dx ? N : l_dx;

	magic[r][c].push_back(ind);
	check.push_back({r, c});
	fireball[ind][1] = r;
	fireball[ind][2] = c;
}

void move()
{
	int r,c,m,s,d;

	for (int i = 0 ; i < fireball.size() ; i++)
	{
		get_magic(i, r, c, m, s, d);
		move_action(i, r, c, s, d);
	}
}

void sum_logic(size_t i, size_t j, int& f_ind)
{
	int m, v, dir, make_dir;
	int ind;

	m = 0;
	v = 0;
	make_dir = 0;
	dir = fireball[magic[i][j][0]][5] % 2;
	for (size_t k = 0 ; k < magic[i][j].size(); k++)
	{
		ind = magic[i][j][k];
		m += fireball[ind][3];
		v += fireball[ind][4];
		if (!make_dir && dir != (fireball[ind][5] % 2))
			make_dir = 1;

	}
	m = std::ceil(m / 5);
	v = std::ceil(v / magic[i][j].size());
	//std::cout << i << " " << j << " " << m << endl;
	if (m == 0)
		return ;
	for (size_t k = 0 ; k < 4 ; k++)
	{
		fireball_tmp.push_back(std::vector<int>());
		if (make_dir) // 다르면
		{
			fireball_tmp[f_ind].push_back(0);
			fireball_tmp[f_ind].push_back(i);
			fireball_tmp[f_ind].push_back(j);
			fireball_tmp[f_ind].push_back(m);
			fireball_tmp[f_ind].push_back(v);
			fireball_tmp[f_ind].push_back(o_d[k]);
		}
		else
		{
			fireball_tmp[f_ind].push_back(0);
			fireball_tmp[f_ind].push_back(i);
			fireball_tmp[f_ind].push_back(j);
			fireball_tmp[f_ind].push_back(m);
			fireball_tmp[f_ind].push_back(v);
			fireball_tmp[f_ind].push_back(s_d[k]);

		}
		f_ind++;
	}
}

void summation()
{
	int y, x, ind;

	ind = 0;
	for(size_t i = 0 ; i < check.size(); i++)
	{
		y = check[i].first;
		x = check[i].second;
		if (visited[y][x])
			continue;
		visited[y][x] = 1;
		if (magic[y][x].size() >= 2)
			sum_logic(y, x, ind);
		else if (magic[y][x].size() == 1)
		{
			fireball_tmp.push_back(std::vector<int>());
			fireball_tmp[ind].push_back(0);
			for (size_t j = 1 ; j <= 5 ; j++)
				fireball_tmp[ind].push_back(fireball[magic[y][x][0]][j]);
			ind++;
		}
	}
}

void solve()
{
	while (K--)
	{
		magic = std::vector<std::vector<std::vector<int> > >(53, std::vector<std::vector<int> >(53));
		fireball_tmp = std::vector<std::vector<int> >();

		memset(visited, 0, sizeof(visited));
		check = std::vector<std::pair<int, int> >();

		move();
		summation();
		fireball = fireball_tmp;
	}
}

void print_val()
{
	int ans = 0;

	for (size_t i = 0 ; i < fireball.size(); i++)
		ans += fireball[i][3];
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}