SWEA 5644 : 무선 충전 (모의 SW 역량테스트)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

무선 충전 링크

 

이후 설명 및 입/출력은 링크 참고

 

MAP의 좌표를 BC로 나타내자.

BC 구조체의 cnt는 MAP[r][c]에서 중복된 BC의 개수이고, bc배열은 BC의 번호가 된다.

각 BC의 성능은 power배열에 저장한다.

typedef struct st1
{
	int bc[10];
	int cnt;
}BC;

BC MAP[MAX][MAX];
int power[10];

 

사용자 A, B의 좌표를 저장할 구조체 배열과 주어진 입력을 기록할 direction 배열을 만든다.

typedef struct st2
{
	int r;
	int c;
}RC;

RC personA, personB;
int directionA[100 + 20];
int directionB[100 + 20];

 

최초로 MAP의 BC들은 0개여야 하므로, cnt = 0으로 초기화한다.

문제에서 주어진 좌표와 배열의 좌표가 다르다. 따라서 column을 먼저 받고, row를 나중에 입력 받는다.

setBC를 이용해 MAP에 모든 BC가 기록되도록 한다.

void input()
{
	for (int r = 1; r <= 10; r++)
		for (int c = 1; c <= 10; c++)
			MAP[r][c].cnt = 0;

	scanf("%d %d", &M, &A);

	for (int i = 0; i < M; i++) scanf("%d", &directionA[i]);
	for (int i = 0; i < M; i++) scanf("%d", &directionB[i]);

	for (int i = 1; i <= A; i++)
	{
		int c, r, range, p;

		scanf("%d %d %d %d\n", &c, &r, &range, &p);

		setBC(r, c, range, i);
		power[i] = p;
	}
}

 

setBC는 주어진 좌표를 기준으로 length만큼 빼고 더해서 사각형을 만든다. 

그리고 주어진 범위보다 작은 경우에만 ( + 좌표를 벗어나지 않는 경우) MAP에 BC를 기록한다.

int abs(int x)
{
	return x > 0 ? x : -x;
}

int getLength(int r1, int c1, int r2, int c2)
{
	return abs(r1 - r2) + abs(c1 - c2);
}

void setBC(int r, int c, int length, int bcNum)
{
	int sr = r - length;
	int sc = c - length;
	int er = r + length;
	int ec = c + length;

	for (int rr = sr; rr <= er; rr++)
	{
		for (int cc = sc; cc <= ec; cc++)
		{
			if (rr < 1 || cc < 1 || rr > 10 || cc > 10) continue;

			int len = getLength(r, c, rr, cc);

			if (len <= length) MAP[rr][cc].bc[MAP[rr][cc].cnt++] = bcNum;
		}
	}
}

 

문제의 예시의 BC 3의 경우, (r, c)가 (3, 6)이고 충전 범위가 2가 되므로

(1, 4) ~ (5, 8) 까지 for문을 돌면서 두 지점 사이의 거리 D가 만족하는 경우만 MAP에 표시되게 된다.

---

이제 사용자 A와 B를 움직이면서 시뮬레이션 한다.

0초인 경우에도 충전이 된다고 하였으므로, getCharge를 먼저 호출하고 이동해야 한다.

그리고 M번 이동 후, 마지막에도 충전을 하므로, for문을 빠져나온 후에 한번 더 충전한다.

/* 0: 움직이지 않음, 1: 위, 2: 오른쪽, 3: 아래, 4: 왼쪽 */
int dr[] = { 0, -1, 0, 1, 0 };
int dc[] = { 0, 0, 1, 0, -1 };

int simulate()
{
	int charge = 0;

	personA.r = 1; personA.c = 1;
	personB.r = 10; personB.c = 10;

	for (int i = 0; i < M; i++)
	{
		charge += getCharge();

		personA.r = personA.r + dr[directionA[i]];
		personA.c = personA.c + dc[directionA[i]];

		personB.r = personB.r + dr[directionB[i]];
		personB.c = personB.c + dc[directionB[i]];
	}

	charge += getCharge();

	return charge;
}

 

충전 함수는 아래와 같다.

먼저 A와 B의 사용자가 MAP[r][c]에 몇 개의 bc가 있는지 알 수 있다.

int ar, ac, br, bc;
int bcCountA, bcCountB;

ar = personA.r; ac = personA.c;
br = personB.r; bc = personB.c;

bcCountA = MAP[ar][ac].cnt;
bcCountB = MAP[br][bc].cnt;

 

A 사용자와 B 사용자 둘 중 한명이라도 bc가 없다면, 남은 1명의 bc 중 가장 큰 값을 고르면 된다.

if (bcCountA == 0 || bcCountB == 0)
{
	int maxChargeA, maxChargeB;

	maxChargeA = 0;
	for (int a = 0; a < bcCountA; a++)
		if (maxChargeA < power[MAP[ar][ac].bc[a]])
			maxChargeA = power[MAP[ar][ac].bc[a]];

	maxChargeB = 0;
	for (int b = 0; b < bcCountB; b++)
		if (maxChargeB < power[MAP[br][bc].bc[b]])
			maxChargeB = power[MAP[br][bc].bc[b]];

	return maxChargeA + maxChargeB;
}

 

둘 다 bc가 여러개인 경우는 2중 for문으로 모든 경우를 선택해보고 가장 charge가 큰 값을 maxCharge에 갱신한다.

int maxCharge = 0;
for (int a = 0; a < bcCountA; a++)
{
	for (int b = 0; b < bcCountB; b++)
	{
		int selectedBC[10] = { 0 };

		selectedBC[MAP[ar][ac].bc[a]] = 1;
		selectedBC[MAP[br][bc].bc[b]] = 1;

		int charge = 0;
		for (int i = 1; i <= 8; i++)
			if (selectedBC[i]) charge += power[i];

		if (maxCharge < charge) maxCharge = charge;
	}
}

 

만약 A가 bc 1, 2에 포함되고, B는 bc 1, 3에 포함된다고 가정하자.

그러면 selectBC는 아래의 경우가 만들어진다.

 

selectBC[1] = 1 → (A, B가 모두 1을 선택한 경우, 물론 이 경우가 maxCharge가 될 수는 없다.)

selectBC[1] = 1, selectBC[2] = 1

selectBC[1] = 1, selectBC[3] = 1

selectBC[2] = 1, selectBC[3] = 1

 

maxCharge는 4가지 경우 중 가장 charge가 큰 경우가 된다.

 

따라서 getCharge는 아래와 같이 구성된다.

int getCharge()
{
	int ar, ac, br, bc;
	int bcCountA, bcCountB;

	ar = personA.r; ac = personA.c;
	br = personB.r; bc = personB.c;

	bcCountA = MAP[ar][ac].cnt;
	bcCountB = MAP[br][bc].cnt;

	if (bcCountA == 0 || bcCountB == 0)
	{
		int maxChargeA, maxChargeB;

		maxChargeA = 0;
		for (int a = 0; a < bcCountA; a++)
			if (maxChargeA < power[MAP[ar][ac].bc[a]])
				maxChargeA = power[MAP[ar][ac].bc[a]];

		maxChargeB = 0;
		for (int b = 0; b < bcCountB; b++)
			if (maxChargeB < power[MAP[br][bc].bc[b]])
				maxChargeB = power[MAP[br][bc].bc[b]];

		return maxChargeA + maxChargeB;
	}

	int maxCharge = 0;
	for (int a = 0; a < bcCountA; a++)
	{
		for (int b = 0; b < bcCountB; b++)
		{
			int selectedBC[10] = { 0 };

			selectedBC[MAP[ar][ac].bc[a]] = 1;
			selectedBC[MAP[br][bc].bc[b]] = 1;

			int charge = 0;
			for (int i = 1; i <= 8; i++)
				if (selectedBC[i]) charge += power[i];

			if (maxCharge < charge) maxCharge = charge;
		}
	}

	return maxCharge;
}

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (10 + 5)

int T, M, A;

typedef struct st1
{
	int bc[10];
	int cnt;
}BC;

BC MAP[MAX][MAX];
int power[10];

typedef struct st2
{
	int r;
	int c;
}RC;

RC personA, personB;
int directionA[100 + 20];
int directionB[100 + 20];

int abs(int x)
{
	return x > 0 ? x : -x;
}

int getLength(int r1, int c1, int r2, int c2)
{
	return abs(r1 - r2) + abs(c1 - c2);
}

void setBC(int r, int c, int length, int bcNum)
{
	int sr = r - length;
	int sc = c - length;
	int er = r + length;
	int ec = c + length;

	for (int rr = sr; rr <= er; rr++)
	{
		for (int cc = sc; cc <= ec; cc++)
		{
			if (rr < 1 || cc < 1 || rr > 10 || cc > 10) continue;

			int len = getLength(r, c, rr, cc);

			if (len <= length) MAP[rr][cc].bc[MAP[rr][cc].cnt++] = bcNum;
		}
	}
}

void input()
{
	for (int r = 1; r <= 10; r++)
		for (int c = 1; c <= 10; c++)
			MAP[r][c].cnt = 0;

	scanf("%d %d", &M, &A);

	for (int i = 0; i < M; i++) scanf("%d", &directionA[i]);
	for (int i = 0; i < M; i++) scanf("%d", &directionB[i]);

	for (int i = 1; i <= A; i++)
	{
		int c, r, range, p;

		scanf("%d %d %d %d\n", &c, &r, &range, &p);

		setBC(r, c, range, i);
		power[i] = p;
	}
}

int getCharge()
{
	int ar, ac, br, bc;
	int bcCountA, bcCountB;

	ar = personA.r; ac = personA.c;
	br = personB.r; bc = personB.c;

	bcCountA = MAP[ar][ac].cnt;
	bcCountB = MAP[br][bc].cnt;

	if (bcCountA == 0 || bcCountB == 0)
	{
		int maxChargeA, maxChargeB;

		maxChargeA = 0;
		for (int a = 0; a < bcCountA; a++)
			if (maxChargeA < power[MAP[ar][ac].bc[a]])
				maxChargeA = power[MAP[ar][ac].bc[a]];

		maxChargeB = 0;
		for (int b = 0; b < bcCountB; b++)
			if (maxChargeB < power[MAP[br][bc].bc[b]])
				maxChargeB = power[MAP[br][bc].bc[b]];

		return maxChargeA + maxChargeB;
	}

	int maxCharge = 0;
	for (int a = 0; a < bcCountA; a++)
	{
		for (int b = 0; b < bcCountB; b++)
		{
			int selectedBC[10] = { 0 };

			selectedBC[MAP[ar][ac].bc[a]] = 1;
			selectedBC[MAP[br][bc].bc[b]] = 1;

			int charge = 0;
			for (int i = 1; i <= 8; i++)
				if (selectedBC[i]) charge += power[i];

			if (maxCharge < charge) maxCharge = charge;
		}
	}

	return maxCharge;
}

/* 0: 움직이지 않음, 1: 위, 2: 오른쪽, 3: 아래, 4: 왼쪽 */
int dr[] = { 0, -1, 0, 1, 0 };
int dc[] = { 0, 0, 1, 0, -1 };

int simulate()
{
	int charge = 0;

	personA.r = 1; personA.c = 1;
	personB.r = 10; personB.c = 10;

	for (int i = 0; i < M; i++)
	{
		charge += getCharge();

		personA.r = personA.r + dr[directionA[i]];
		personA.c = personA.c + dc[directionA[i]];

		personB.r = personB.r + dr[directionB[i]];
		personB.c = personB.c + dc[directionB[i]];
	}

	charge += getCharge();

	return charge;
}

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

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

	return 0;
}