[SWEA 5644] 무선 충전

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
int T;
int M, A;	// 총 이동시간, BC 개수
int ax = 1, ay = 1;
int bx = 10, by = 10;

int move_a[100 + 2];
int move_b[100 + 2];

struct _st
{
	int x, y;
	int C;
	int P;
}BC[8 + 2];

std::vector<int> near_a;
std::vector<int> near_b;

// dir
// 0stay 1상 2우 3하 4좌 
int dir_x[5] = { 0, -1, 0, 1, 0 };
int dir_y[5] = { 0, 0, 1, 0, -1 };



void input()
{
	// init
	ax = ay = 1;
	bx = by = 10;
	memset(move_a, 0, sizeof(move_a));
	memset(move_b, 0, sizeof(move_b));
	memset(BC, 0, sizeof(BC));

	scanf("%d %d", &M, &A);
	for (int i = 1; i <= M; i++) scanf("%d", &move_a[i]);
	for (int j = 1; j <= M; j++) scanf("%d", &move_b[j]);

	for (int i = 1; i <= A; i++) {
		scanf("%d %d %d %d", &BC[i].y, &BC[i].x, &BC[i].C, &BC[i].P);
	}
}


void GO_ab(int t)
{
	// init
	near_a.clear();
	near_b.clear();

	for (int i = 1; i <= A; i++) {
		if (abs(BC[i].x - ax) + abs(BC[i].y - ay) <= BC[i].C) near_a.push_back(i);
		if (abs(BC[i].x - bx) + abs(BC[i].y - by) <= BC[i].C) near_b.push_back(i);
	}

	// next
	ax += dir_x[move_a[t + 1]];
	ay += dir_y[move_a[t + 1]];
	bx += dir_x[move_b[t + 1]];
	by += dir_y[move_b[t + 1]];
}



int compare_max()
{
	int max = 0;
	// 둘 다 없을 때
	if (near_a.empty() && near_b.empty()) return 0;

	// A만 있을 때 
	if (!near_a.empty() && near_b.empty()) {
		for (int place : near_a) {
			if (max < BC[place].P) max = BC[place].P;
		}
		return max;
	}

	// B만 있을 때 
	if (near_a.empty() && !near_b.empty()) {
		for (int place : near_b) {
			if (max < BC[place].P) max = BC[place].P;
		}
		return max;
	}

	// 둘 다 있을 때 
	if (!near_a.empty() && !near_b.empty()) {
		for (int p1 : near_a) {
			for (int p2 : near_b) {
				if (p1 == p2) {
					if (max < BC[p1].P) max = BC[p1].P;
				}
				else {
					if (max < BC[p1].P + BC[p2].P) max = BC[p1].P + BC[p2].P;
				}
			}
		}
		return max;
	}
}


int simulation()
{
	int total = 0;
	for (int time = 0; time <= M; time++) {
		GO_ab(time);
		total += compare_max();
		//printf("(%d %d) (%d %d) >> %d\n", ax, ay, bx, by, compare_max());
	}
	return total;
}




int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		input();
		int ans = simulation();
		printf("#%d %d\n",t, ans);
	}
	return 0;
}

처음에 재귀로 짜다가 1번 테케부터 안나와서 덮고 다시 푼 문제.. 

그냥 쉽게 생각하면 되는 문제였다. 각 시간에서 얻을 수 있는 최대 성능을 구하는 것은 a와 b에 가까운 BC 다 벡터에 담아주고, for 문 돌리면서 최댓값 갱신해주면 된다. 

어렵게 생각하지말자.. 쉽게 생각하자 ..