#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
struct Atom {
int r, c, m, s, d;
};
struct Coord {
int m, s, d;
};
int N, M, K;
// 현재 원자
vector<Coord> MAP[55][55];
vector<Atom> nowA;
vector<Atom> nextA;
// ↑, ↗, →, ↘, ↓, ↙, ←, ↖
int dr[] = { -1,-1,0,1,1,1,0,-1 };
int dc[] = { 0,1,1,1,0,-1,-1,-1 };
void move(Atom &a)
{
// 항상 양수로 만들어서 나눗셈 연산 !!
a.r = (a.r + dr[a.d] * a.s + N * a.s) % N;
a.c = (a.c + dc[a.d] * a.s + N * a.s) % N;
MAP[a.r][a.c].push_back({ a.m, a.s, a.d });
}
void CLEAR()
{
memset(MAP, 0, sizeof(MAP));
}
void INPUT()
{
cin >> N >> M >> K;
for (int i = 1; i <= M; i++)
{
int x, y, m, s, d;
cin >> x >> y >> m >> s >> d;
nowA.push_back({ x - 1, y - 1, m, s, d });
}
}
void SOLVE()
{
int time = 0;
while (time < K)
{
memset(MAP, 0, sizeof(MAP));
nextA.clear();
// 이동
for (int i = 0; i < nowA.size(); i++)
move(nowA[i]);
// 원자 나누기
nowA.clear();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j].size() == 0) continue;
else if (MAP[i][j].size() == 1)
{
Coord A = MAP[i][j][0];
nextA.push_back({i, j, A.m, A.s, A.d});
}
else
{
int size_atom = MAP[i][j].size();
int m = 0;
int s = 0;
int d = MAP[i][j][0].d;
int flag_dir = 0;
for (int k = 0; k < size_atom; k++)
{
m += MAP[i][j][k].m;
s += MAP[i][j][k].s;
// 방향이 다르면 대각선으로
if (d % 2 != MAP[i][j][k].d %2)
flag_dir++ ;
}
// 질량이 5 이하면 넘어감 (질량 0 소멸)
if (m >= 5)
{
// 방향 동일 - 상하좌우
if (flag_dir == 0)
{
for (int k = 0; k < 4; k++)
{
nextA.push_back({ i, j, m / 5, s / size_atom, k * 2 });
}
}
// 방향 상이 - 대각선
else
{
for (int k = 0; k < 4; k++)
{
nextA.push_back({ i, j, m / 5, s / size_atom, k * 2 + 1 });
}
}
}
}
}
}
nowA = nextA;
time++;
}
int answer = 0;
for (int i = 0; i < nowA.size(); i++)
{
answer += nowA[i].m;
}
cout << answer << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}
📌 memo
😊 MAP을 이어진 것처럼 만드는 법!
나눗셈연산!!
예를 들어
1. 아래로 갈때
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 0) - (0, 0)
(5, 0) - (1, 0)
...
2. 위로 갈 때
(0, 0)
(-1, 0) - (3, 0)
(-2, 0) - (2, 0)
(-3, 0) - (1, 0)
...
이러한 형태로 이어지기 때문에 나머지 연산으로 해결가능!!
=> 이 문제에서의 공식
a.r = (a.r + dr[a.d] x a.s + N x a.s) % N
a.c = (a.c + dc[a.d] x a.s + N x a.s) % N