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

출처:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

SW Expert Academy

시뮬레이션 구현 문제이다.

 

두명의 사용자 A,B가 각각 (1,1), (10,10)에서 출발하여 초기 명령에 따라 움직인다. 사용자가 무선충전기 BC 범위 안에 있을때 해당 BC의 충전량만큼 충전을 하게 되고 도착지점에 도착했을때 충전 값의 최댓값을 출력하는 문제이다.

 

그리고 사용자가 충전하는 경우는 다음과 같다.

1. 아무것도 없으면 충전없이 그냥 지나간다.

 

2. 사용자 A,B 중 한명만 BC 영역에 있으면 그사람이 속한 BC영역의 BC중 최댓값만 구하면 된다.

 

3. 사용자 둘다 임의의 BC범위 안에 들어와 있을 경우

예를들어 1. 사용자 A가 BC 1,2,3에 속해 있고 사용자 B가 BC 2,3,4 에 속해 있으면 12 13 14 22 23 24 32 33 34 조합이 가능하고 이들 중 22, 33은 같은 BC에 속하므로 균등분배를 적용하여 12 13... 34 중 최댓값을 저장하면된다.

 

소스코드

 

	// #s 5644. [모의 SW 역량테스트] 무선 충전
	#include <iostream>
	#include <vector>
	#include <queue>
	#include <cstring>
	#define endl '\n'
	using namespace std;
	int dir[5][2] = { {0,0}, { 0,-1 }, {1,0}, {0,1}, {-1,0} };//상 우 하 좌
	typedef struct info {
	int apno, energy;
	}info;
	typedef struct xy {
	int x, y;
	}xy;
	int MAX(int a, int b) {
	return a > b ? a : b;
	}
	int main() {
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
	int A[101];
	int B[101];
	vector <info> arr[11][11];
	int cnt, ap;
	cin >> cnt >> ap;
	for (int i = 0; i < cnt; i++) {
	cin >> A[i];
	}
	for (int i = 0; i < cnt; i++) {
	cin >> B[i];
	}
	// ap 범위와 값 지정
	for (int i = 0; i < ap; i++) {
	int stx, sty, s, energy;
	int visit[11][11];
	memset(visit, 0, sizeof(visit));
	int TIME = 0;
	cin >> stx >> sty >> s >> energy;// (x,y) , 충전 영역, 충전 양
	queue <xy>q;
	q.push({ stx,sty });
	visit[stx][sty] = true;
	arr[stx][sty].push_back({ i,energy });
	while (!q.empty()) {
	int size = q.size();
	TIME++;
	//TIME 이 s만큼 도달하면 종료
	while (size--) {
	int fx = q.front().x, fy = q.front().y;
	q.pop();
	for (int d = 1; d <= 4; d++) {
	int nx = fx + dir[d][0];
	int ny = fy + dir[d][1];
	if (nx <= 0 || nx > 10 || ny <= 0 || ny > 10)continue;
	if (visit[nx][ny])continue;
	visit[nx][ny] = true;
	q.push({ nx,ny });
	arr[nx][ny].push_back({ i,energy });
	}
	}
	if (TIME == s)break;
	}
	//for (int y = 1; y <= 10; y++) {
	// for (int x = 1; x <= 10; x++) {
	// cout << visit[x][y] << " ";
	// }cout << endl;
	//}cout << endl;
	}
	int ax = 1, ay = 1;
	int bx = 10, by = 10;
	int sum = 0;
	int c = 0;
	while(true){
	int Ad = A[c];
	int Bd = B[c];
	//사용자가 충전하는 경우는 다음과 같다.
	//1. 아무것도 없으면 충전없이 그냥 지나간다.
	//2. 사용자 A,B 중 한명만 BC 영역에 있으면 그사람이 속한 BC영역의 BC중 최댓값만 구하면 된다.
	if (arr[ax][ay].size()==0|| arr[bx][by].size() ==0) {
	int maxx = 0;
	for (int i = 0; i < arr[ax][ay].size(); i++) {
	maxx = MAX(maxx, arr[ax][ay][i].energy);
	}
	for (int i = 0; i < arr[bx][by].size(); i++) {
	maxx = MAX(maxx, arr[bx][by][i].energy);
	}
	sum += maxx;
	}
	//3. 사용자 둘다 임의의 BC범위 안에 들어와 있을 경우
	//예를들어 1. 사용자 A가 BC 1,2,3에 속해 있고 사용자 B가 BC 2,3,4 에 속해 있으면
	//12 13 14 22 23 24 32 33 34 조합이 가능하고 이들 중 22, 33은 같은 BC에 속하므로 균등분배를 적용하여
	//12 13... 34 중 최댓값을 저장하면된다.
	else {
	int maxx = 0;
	int temp = 0;
	for (int i = 0; i < arr[ax][ay].size(); i++) {
	int apA = arr[ax][ay][i].apno;
	int energyA = arr[ax][ay][i].energy;
	for (int j = 0; j < arr[bx][by].size(); j++) {
	int apB = arr[bx][by][j].apno;
	int energyB = arr[bx][by][j].energy;
	temp = energyA + energyB;
	if (apA == apB)temp /= 2;
	maxx = MAX(maxx, temp);
	}
	}
	sum += maxx;
	}
	//cout << "ax " << ax << " ay " << ay << " bx " << bx << " by " << by << endl;
	//cout << sum << endl;
	//종료
	if (c >= cnt)break;
	ax += dir[Ad][0], ay += dir[Ad][1];
	bx += dir[Bd][0], by += dir[Bd][1];
	c++;
	}
	cout << "#" << t << " " << sum << endl;
	}
	}

view raw [SWEA]5644무선충전.cpp hosted with ❤ by GitHub