5644. 무선 충전

#define ABS(X) ((X > 0) ? X : -X)

using namespace std;

typedef struct
{
	int y, x, c, p;
}BC;

static int M, A;
static int d[5][2] = {
	0, 0, //dont move
	-1, 0, //up
	0, 1, //right
	1, 0, //down
	0, -1 //left
}; //문제에서 제시하는 방향을 정확히 볼 것,

static int find_max(vector<int>& used, const vector<BC> & BCs)
{
	int max = 0;
	//used가 사용할 수 있는 BC들의 리스트 중 충전양이 최대인 것을 찾는다.
	for (int i = 0; i < used.size(); i++)
	{
		int idx = used[i];
		if (BCs[idx].p > max)
			max = BCs[idx].p;
	}
	return max;
}

static int check(int (*u)[2], const vector<BC>& BCs)
{
	int dy, dx, cover, ret = 0, max = 0;
	vector<int> used[2];

	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < BCs.size(); j++)
		{
			dy = u[i][0] - BCs[j].y;
			dx = u[i][1] - BCs[j].x;
			cover = ABS(dy) + ABS(dx);
			//커버리지 안에 들어 간다면 해당 BC의 인덱스를 푸쉬
			if (cover <= BCs[j].c)
				used[i].push_back(j);
		}
	}

	if (used[0].empty() && used[1].empty())
		return 0;
	else if (used[0].empty())
		return find_max(used[1], BCs);
	else if (used[1].empty())
		return find_max(used[0], BCs);
	else
	{
		//모든 조합을 만들어 본다.
		for (int i = 0; i < used[0].size(); i++)
		{
			for (int j = 0; j < used[1].size(); j++)
			{
				int u1 = used[0][i], u2 = used[1][j];
				int tmp = 0;

				if (u1 != u2)
					tmp = BCs[u1].p + BCs[u2].p;
				else
					tmp = BCs[u1].p;

				if (tmp > ret)
					ret = tmp;
			}
		}
	}

	return ret;
}

static int solution()
{
	queue<int> user[2];
	vector<BC> BCs;
	int ans = 0;
	int u[2][2] = {
		1, 1,
		10, 10
	};
	
	scanf("%d %d", &M, &A);
	for (int u = 0; u < 2; u++)
	{
		for (int i = 0; i < M; i++)
		{
			int dir;
			scanf("%d", &dir);
			user[u].push(dir);
		}
	}
	
	for (int i = 0; i < A; i++)
	{
		int x, y, c, p;
		scanf("%d %d %d %d", &x, &y, &c, &p); //입력은 x, y로 들어온다.
		BCs.push_back({ y, x, c, p }); //그래서 순서를 바꾸어서 입력
	}

	ans = check(u, BCs); //t == 0
	while (user[0].size()) //user의 이동방향은 pair함.
	{
		//모든 user의 위치 정보 갱신
		for (int i = 0; i < 2; i++)
		{
			int dir = user[i].front();
			user[i].pop();
			u[i][0] += d[dir][0];
			u[i][1] += d[dir][1]; 
		}
		
		ans += check(u, BCs);
	}

	return ans;
}

이 문제에서는 BC의 위치에 대해서 (y, x)로 입력이 주어지는것이 아니라 (x, y)로 주어진다.

그래서 입력시에는 최대한 해당 형식을 따르고, 그 이후 부터는 내가 선호하는 (y, x) 형식으로 바꾸어서 데이터를 저장하였다.

 

그리고 예전에 풀었던 방식과는 다른 방식으로 풀었다. 예전에는 BC의 영역을 이차원 배열에 저장해놓아서 사용자 A, B가 움직일 때 마다 어느 영역에 존재하는지 알 수 있게 하였는데,

여기서는 그렇게 하지 않았다.

 

check() 를 보면 각각에 사용자에 대해서 모든 BC에 대해 해당 영역에 존재하는지 확인하고, 영역에 존재하면 해당 BC의 인덱스를 각 사용자에 할당된 vector에 삽입한다.

 

이 후, 두 vector가 모두 비어있으면 두 사용자 모두 충전을 할 수 없으므로 0이 반환되고,

하나만 비어있으면 그 한명이 연결 하여 충전할 수 있는 BC중 최대 충전량을 반환한다.

그리고 마지막은 둘다 비어있지 않은 경우인데,

이 때에는 이중 for문을 이용하여 모든 경우를 다 체크해본다. 이렇게 하는 것이 문제를 정확하게 풀 수 있기 때문이다.

 

//주의사항 및 정리

1. 문제를 똑바로 읽을 것, 방향 정보를 잘못 체크하여 문제를 다시 푸는데도 어려움이 있었다.

2. 매크로 함수 사용 시 변수에 값을 담아 전달 하여 사용할 것, 매크로 함수 특성 상 괄호를 많이 친다 하여도 내가 예상못한 상황이 존재할 수 있다.

3. vector배열 사용 시 인덱스 사용 똑바로 할 것, 디버깅 시 pNext같은 것이 나와서 에러가 발생하면 거의 대부분 이 문제이다. ex) vector<int> v[3]; v[5].push_back(0); -> 이러면 VS기준 디버깅시 위와 같은 코드가 나온다.