SWEA 5644번 [모의 SW 역량테스트] 무선 충전 C++ 구현, 시뮬레이션

리뷰

2D 시뮬레이션을 통해 사용자의 이동에 따른 충전량의 최대 합계를 구하는 문제

 

SW Expert Academy

 

BC

위치(x, y)와 충전 범위 c, 성능 p로 이루어진 구조체로 정의해 준다.

BC의 충전 범위는 겹치는 경우가 있고, 겹쳐지지 않는 경우가 있다.

BC의 개수는 1 ~ 8개 존재할 수 있으며, 같은 위치에 2개 이상의 BC가 설치된 경우는 없다.

사용자

사용자는 총 2명이고, 사용자 A는 0, 0 좌표 사용자 B는 9, 9좌표에서 시작한다. 맵은 10 * 10 고정

총 이동 시간 m은 20이상 100 이하의 정수이다, 사용자 A와 B가 동시에 같은 위치로 이동할 수 있다.

 

시뮬레이션

시간에 따라서 사용자가 움직인다, BC 충전 범위 안에 있을 경우 BC의 성능 p만큼 배터리를 충전할 수 있다.

만약 같은 BC 안에 두명의 사용자가 있을 경우 충전 양을 균등하게 분배한다.

모든 사용자가 충전한 양의 합의 최댓값을 구하기

 

문제 풀이

테스트케이스의 수 t를 입력 받고 각 테케 실행 후 init(), input(), solution() 함수를 실행해 준다.

1. init()

1. 테스트 케이스 마다 ans를 0으로, BC 정보를 저장했던 dic를 초기화 해준다.

 

2. input()

1. m과 a값을 받아오고, 사용자A, B가 움직인 경로와 BC 정보를 받아온 뒤 map에 할당해 준다.

 

3. solution()

1. 시간의 흐름에 따른 좌표 이동을 시뮬레이션 해준다.
2. 사용자A와 B의 시작 좌표를 각각 (0, 0), (9, 9)로 초기화 해주고 해당 위치에서의 충전량을 ans에 더해준다.
3. 이후 각각 사용자의 위치 변화에 따른 좌표값 수정 후 해당 위치에서의 충전량을 ans에 더해준다.
4. 충전량을 더하는 함수는 calc를 사용해 주었다.

 

4. calc(int ax, int ay, int bx, int by)

1. A와 B의 좌표를 매개변수로 받아오고, 모든 BC에 대해 탐색을 완료한 후 최대값을 리턴해 준다.
2. max_charge를 -1로 초기화 해주고, 모든 BC를 돌며 가장 큰 값으로 max_charge를 최신화 해준다.
3. for문이 종료된 후 max_charge를 리턴해 준다.
4. 최대값을 구하는 데엔 check 함수를 사용해 주었다.

 

5. calc(int index, int x, int y)

1. index 번째의 BC의 범위에 해당 사용자가 위치해 있다면 BC의 충전량을 리턴하고, 범위에 있지 않으면 0을 리턴
2. 범위를 구하는 공식은 문제에 나와 있다.

 

 

시뮬레이션이 완료된 후 각 테스트 케이스 마다 ans 값을 출력해 주면 된다.

 

참고 사항

BC의 좌표값이 x,y가 반대로, 2차 배열 index보다 1 크게 입력된다. 이점에 유의

 

정답 코드

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

vector<int> lst[10][10];
int t, m, a, ans;
int userA[100];
int userB[100];

int dx[] = { 0, -1, 0, 1, 0 };
int dy[] = { 0, 0, 1, 0, -1 };

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

unordered_map<int, BC> dic;

void init() {
	ans = 0;
	dic.clear();
}

void input() {
	cin >> m >> a;
	for (int i = 0; i < m; i++) cin >> userA[i];
	for (int i = 0; i < m; i++) cin >> userB[i];
	for (int i = 0; i < a; i++) {
		int x, y, c, p;
		cin >> y >> x >> c >> p;
		dic[i] = { x - 1, y - 1, c, p };
	}
}

int check(int index, int x, int y) {
	// 어떤 BC인지 확인
	int cx = dic[index].x, cy = dic[index].y, cc = dic[index].c, cp = dic[index].p;

	// 범위 계산
	int dist = abs(x - cx) + abs(y - cy);

	// 범위 안에 들어왔다면 충전량 도출
	if (dist <= cc) return cp;
	return 0;
}

int calc(int ax, int ay, int bx, int by) {
	// 현재 좌표에서 최대 충전량 계산
	int max_charge = -1;
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < a; j++) {
			int sum = 0;
			int cA = check(i, ax, ay);
			int cB = check(j, bx, by);
			if (i != j) sum = cA + cB;
			else sum = max(cA, cB);
			if (sum > max_charge) max_charge = sum;
		}
	}
	return max_charge;
}

void solution() {
	// 시간에 흐름에 따른 좌표 이동
	int ax = 0, ay = 0;
	int bx = 9, by = 9;
	ans += calc(ax, ay, bx, by);
	for (int i = 0; i < m; i++) {
		ax += dx[userA[i]];
		ay += dy[userA[i]];
		bx += dx[userB[i]];
		by += dy[userB[i]];
		ans += calc(ax, ay, bx, by);
	}
}

int main() {
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		init(); // 초기화
		input(); // 입력
		solution(); // 시뮬레이션
		cout << "#" << tc << " " << ans << "\n";
	}
}