SWEA 5644번: [모의 SW 역량테스트] 무선 충전

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

SW Expert Academy

 

모의 역테 문제 중 비교적 쉬운 편이었던 문제 

그림과 같이 AP는 고유의 거리와 성능을 가지고 있고, 그 범위는 겹칠 수 있다

A와 B 두 단말기의 초기 위치와 이동 경로를 주어졌을 때, 충전량을 구하는 문제이다

 

이 때, 경우의 수를 크게 두 개로 나눌 수 있다

1️⃣ A와 B가 위치한 BC 범위가 겹칠 때

2️⃣ A와 B가 위치한 BC 범위가 겹치지 않을 때

 

2번은 두 위치의 최대 충전량을 각각 구해서 더해주면 된다

1번은 이제 또 3가지의 경우로 나뉘는데, 그림과 같다

AP1>AP2>AP3 순서대로 성능이 좋다고 가정

1️⃣ A와 B가 한 BC만을 공유할 때

👉 AP1의 성능을 2로 나누어 A와 B가 가져야 하기 때문에 총 성능은 AP1의 C와 같다

2️⃣ A 혹은 B가 다른 BC에 걸쳐져있을 때

👉 1번의 경우처럼 C1(AP1의 성능) 보다는, C1 + C2가 무조건 크기 때문에 2번의 경우에는 총 성능은 C1+C2와 같다

3️⃣ A와 B가 위치한 두 좌표가 모두 두개 이상의 BC가 걸쳐져있을 때

👉 AP2와 AP3 중 성능이 큰 AP를 골라 C1와 더한 것을 총 성능으로 한다

 

개인적으로는 난이도를 더 높여서 A,B 말고도 여러 단말기를 추가한다거나 시간에 따른 성능을 다르게 했어도 좋을 것 같다

 

소스코드: 

#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
int tc, m, a, user[2][105], dx[] = { 0,0,1,0,-1 }, dy[] = { 0,-1,0,1,0 };
typedef struct {
	int x, y;
}point;
typedef struct {
	point p;
	int c, f;
}ap;
point A = { 0,0 }, B = { 9,9 };
vector<pair<int,int>> map[10][10];
bool cmp(pair<int,int> a, pair<int, int> b) {
	return a.second > b.second;
}

int bc() {
	int ca=0, cb=0;
	vector<pair<int, int>> &va = map[A.y][A.x],&vb= map[B.y][B.x];
	
	if (!va.empty() && !vb.empty())
		if (va[0].first == vb[0].first) {
			if (va.size() == 1 && vb.size() == 1)
				return va[0].second;	//둘다 같은 범위 내에 잇고, AP가 1개 뿐이라면
			else if (va.size() != 1 && vb.size() != 1)
				return va[0].second + max(va[1].second, vb[1].second);
			else if (va.size() != 1)
				return va[0].second + va[1].second;
			else
				return va[0].second + vb[1].second;
		}

	if (!va.empty())ca = va[0].second;
	if (!vb.empty())cb = vb[0].second;

	return ca + cb;
}

int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		int ans = 0, t = 0;
		vector<ap> v; A = { 0,0 }, B = { 9,9 };
		scanf("%d%d", &m, &a);
		for (int i = 0; i < 2; i++)
			for (int j = 1, k; j <= m; j++)
				scanf("%d", &user[i][j]);

		for (int i = 0, x, y, c, p; i < a; i++) {
			scanf("%d%d%d%d", &x, &y, &c, &p);
			v.push_back({ {x - 1,y - 1},c,p });
		}

		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 10; j++) {//모든 좌표
				int index = 1;
				for (auto k : v) {
					int dis = abs(i - k.p.y) + abs(j - k.p.x);
					if (dis <= k.c)	//사정거리 내에 잇다면
						map[i][j].push_back({ index,k.f });
					index++;
				}

				if (map[i][j].size() > 1) {
					sort(map[i][j].begin(), map[i][j].end(), cmp);
				}	//capacity 내림차순 정렬

			}

		ans += bc();
		while (m--) {
			t++;
			A.x += dx[user[0][t]]; A.y += dy[user[0][t]];
			B.x += dx[user[1][t]]; B.y += dy[user[1][t]];
			int k= bc();
			ans += k;	
		}

		for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++)map[i][j].clear();
		printf("#%d %d\n", T, ans);
	}
	return 0;
}

이제는 테스트 케이스 생성하고 문제 정의 확실히 해서 1솔 안에 패스하는 연습을 해야할 것 같다

^-T

삼성 역량테스트 D-26