[코드트리] 원자 충돌

rhkr9080·2023년 9월 16일
0

코드트리

목록 보기
24/29

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/atom-collision/submissions?page=2&pageSize=20

💻 문제 풀이 : C++

#### 📌 정답풀이
#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

profile
공부방

0개의 댓글

Powered by GraphCDN, the GraphQL CDN