5644 무선 충전

1초 단위마다 바뀐 위치에서 얻을 수 있는 최대값을 끝날때까지 더해주면 된다.

 

최대값 구하는 방법 :

1. A와 B가 현재 위치에서 가능한 충전량의 최대값 1등, 2등을 찾는다.

 

2.

A가 0개 연결된 경우 - B가 0개 연결된 경우, 1개 연결된 경우, 2개 연결된 경우

A가 1개 연결된 경우 - B가 0개 연결된 경우, 1개 연결된 경우, 2개 연결된 경우

A가 2개 연결된 경우 - B가 0개 연결된 경우, 1개 연결된 경우, 2개 연결된 경우

9가지 경우로 나누어 최대값을 찾아 더해준다.

 

 

#include <stdio.h>
#include <algorithm>
using namespace std;

struct Battery {
	int x;
	int y;
	int c; //충전 범위
	int p; //처리량
};

struct Node {
	int x;
	int y;
};

int t, m, a, res;
int a_move[102];
int b_move[102];
Battery bs[10];
int dx[] = { 0, 0, 1, 0, -1 };
int dy[] = { 0, -1, 0, 1, 0 };
Node a_cur, b_cur;

int getDist(Node node, int idx) {
	int x = abs(node.x - bs[idx].x);
	int y = abs(node.y - bs[idx].y);
	return x + y;
}

void addResult(int a_first, int a_first_idx, int a_second, int b_first, int b_first_idx, int b_second) {
	//a가 0개
	if (a_first == 0) {
		res += b_first;
	}
	//a가 1개
	else if (a_first != 0 && a_second == 0) {
		//b가 0개
		if (b_first == 0) {
			res += a_first;
		}
		//b가 1개
		else if (b_first != 0 && b_second == 0) {
			if (a_first_idx == b_first_idx) {
				res += a_first;
			}
			else {
				res += a_first + b_first;
			}
		}
		//b가 2개
		else if (b_second != 0) {
			if (a_first_idx == b_first_idx) {
				res += a_first + b_second;
			}
			else {
				res += a_first + b_first;
			}
		}
	}
	//a가 2개
	else if (a_second != 0) {
		//b가 0개
		if (b_first == 0) {
			res += a_first;
		}
		//b가 1개
		else if (b_first != 0 && b_second == 0) {
			if (a_first_idx == b_first_idx) {
				res += b_first + a_second;
			}
			else {
				res += b_first + a_first;
			}
		}
		//b가 2개
		else if (b_second != 0) {
			if (a_first_idx == b_first_idx) {
				res += a_first + max(a_second, b_second);
			}
			else {
				res += a_first + b_first;
			}
		}
	}
}

int main() {

	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {
		scanf("%d %d", &m, &a);
		for (int i = 0; i < m; i++) {
			scanf("%d", &a_move[i]);
		}
		for (int i = 0; i < m; i++) {
			scanf("%d", &b_move[i]);
		}
		for (int i = 0; i < a; i++) {
			scanf("%d %d %d %d", &bs[i].x, &bs[i].y, &bs[i].c, &bs[i].p);
		}

		res = 0;

		//위치 초기화
		a_cur.x = 1;
		a_cur.y = 1;
		b_cur.x = 10;
		b_cur.y = 10;

		//처음 위치에서 충전량 계산
		int a_first = 0;
		int a_first_idx = 0;
		int a_second = 0;
		int b_first = 0;
		int b_first_idx = 0;
		int b_second = 0;

		for (int i = 0; i < a; i++) {
			int dist = getDist(a_cur, i);
			if (bs[i].c >= dist) {
				if (a_first < bs[i].p) {
					a_second = a_first;
					a_first = bs[i].p;
					a_first_idx = i;
				}
				else {
					if (a_second < bs[i].p) {
						a_second = bs[i].p;
					}
				}
			}

			dist = getDist(b_cur, i);
			if (bs[i].c >= dist) {
				if (b_first < bs[i].p) {
					b_second = b_first;
					b_first = bs[i].p;
					b_first_idx = i;
				}
				else {
					if (b_second < bs[i].p) {
						b_second = bs[i].p;
					}
				}
			}
		}

		addResult(a_first, a_first_idx, a_second, b_first, b_first_idx, b_second);

		//이동 후 충전량 계산
		for (int i = 0; i < m; i++) {
			a_cur.x = a_cur.x + dx[a_move[i]];
			a_cur.y = a_cur.y + dy[a_move[i]];

			b_cur.x = b_cur.x + dx[b_move[i]];
			b_cur.y = b_cur.y + dy[b_move[i]];

			a_first = 0;
			a_first_idx = 0;
			a_second = 0;
			b_first = 0;
			b_first_idx = 0;
			b_second = 0;

			for (int j = 0; j < a; j++) {
				int dist = getDist(a_cur, j);
				if (bs[j].c >= dist) {
					if (a_first < bs[j].p) {
						a_second = a_first;
						a_first = bs[j].p;
						a_first_idx = j;
					}
					else {
						if (a_second < bs[j].p) {
							a_second = bs[j].p;
						}
					}
				}

				dist = getDist(b_cur, j);
				if (bs[j].c >= dist) {
					if (b_first < bs[j].p) {
						b_second = b_first;
						b_first = bs[j].p;
						b_first_idx = j;
					}
					else {
						if (b_second < bs[j].p) {
							b_second = bs[j].p;
						}
					}
				}
			}

			addResult(a_first, a_first_idx, a_second, b_first, b_first_idx, b_second);
		}

		printf("#%d %d\n", tc, res);
	}
}