SW 5644. [모의 SW 역량테스트] 무선 충전

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE

SW Expert Academy

 

DFS로 풀다가 시간초과가 발생하는 것을 보고 그리디로 풀면 된다는 것을 깨우침.

쉽진 않았으나 , 풀만한 문제였다.

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int M, APP;

struct Node {
	int x;
	int y;
	int c;
	int p;
};

Node AP[9];
int A[101];
int B[101];

int ay, ax;
int by, bx;

int result;

void moveA(int cur)
{
	if (A[cur] == 0)
	{

	}
	else if (A[cur] == 1)
	{
		if (ay - 1 >= 1)
		{
			ay--;
		}
	}
	else if (A[cur] == 2)
	{
		if (ax + 1 <= 10)
		{
			ax++;
		}
	}
	else if (A[cur] == 3)
	{
		if (ay + 1 <= 10)
		{
			ay++;
		}
	}
	else if (A[cur] == 4)
	{
		if (ax - 1 >= 1)
		{
			ax--;
		}
	}

}

void moveB(int cur)
{
	if (B[cur] == 0)
	{

	}
	else if (B[cur] == 1)
	{
		if (by - 1 >= 1)
		{
			by--;
		}
	}
	else if (B[cur] == 2)
	{
		if (bx + 1 <= 10)
		{
			bx++;
		}
	}
	else if (B[cur] == 3)
	{
		if (by + 1 <= 10)
		{
			by++;
		}
	}
	else if (B[cur] == 4)
	{
		if (bx - 1 >= 1)
		{
			bx--;
		}
	}

}

void GO()
{
	
	int cur = 0;
	int costa = 0;
	int costb = 0;

	while (cur <= M)
	{
		
		moveA(cur);
		moveB(cur);

		vector<int> a;
		vector<int> b;

		for (int i = 1; i <= APP; i++)
		{
			if (abs(AP[i].x - ax) + abs(AP[i].y - ay) <= AP[i].c)
			{
				a.push_back(i);
			}
			if (abs(AP[i].x - bx) + abs(AP[i].y - by) <= AP[i].c)
			{
				b.push_back(i);
			}
		}

		if (!a.empty() && b.empty())
		{
			int maxa = 0;
			
			for (int j = 0; j < a.size(); j++)
			{
				if (AP[a[j]].p > maxa)
				{
					maxa = AP[a[j]].p;
				}
			}

			costa += maxa;
		}
		else if (a.empty() && !b.empty())
		{
			int maxb = 0;

			for (int j = 0; j < b.size(); j++)
			{
				if (AP[b[j]].p > maxb)
				{
					maxb = AP[b[j]].p;
				}
			}

			costb += maxb;
		}
		else if (!a.empty() && !b.empty())
		{
			int maxa = 0;
			int maxb = 0;

			for (int i = 0; i < a.size(); i++)
			{
				for (int j = 0; j < b.size(); j++)
				{

					if (a[i] == b[j])
					{
						if (maxa + maxb < AP[a[i]].p/2 + AP[b[j]].p/2)
						{
							maxa = AP[a[i]].p/2;
							maxb = AP[b[j]].p/2;
						}

					}
					else
					{
						if (maxa + maxb < AP[a[i]].p + AP[b[j]].p)
						{
							maxa = AP[a[i]].p;
							maxb = AP[b[j]].p;
						}
					}
					
				}
			}

			costa += maxa;
			costb += maxb;
		}


		cur++;

	}
	
	result = costa + costb;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> M >> APP;
		ax = 1;
		ay = 1;
		bx = 10;
		by = 10;
		result = 0;

		for (int i = 1; i <= M; i++)
		{
			cin >> A[i];
		}

		for (int i = 1; i <= M; i++)
		{
			cin >> B[i];
		}

		for (int i = 1; i <= APP; i++)
		{
			int x, y, c, p;
			cin >> x >> y >> c >> p;
			AP[i] = { x,y,c,p };
		}

		GO();

		cout << "#" << test_case << " " << result << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}