SWEA 2117 : 홈 방범 서비스 (모의 SW 역량테스트)

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

홈 방범 서비스 링크

 

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

 

 

가능한 큰 K부터 이익이 있는 한, 가장 큰 집의 수를 찾으면 된다.

N x N의 MAP을 모두 서비스하기 위한 K는 N + 1이므로, K = N + 1의 영역부터 영역을 줄여나간다.

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	K = N + 1;
}

 

K에 대한 운영 비용 주어진 공식대로 cost 배열에 저장한다.

그리고 서비스 영역을 만들기 위해 AREA 배열에 해당하는 영역을 저장한다.

row가 1에서 k가 될 때 까지는 column이 양 옆으로 늘어나고, k + 1부터는 줄어들게 만든다.

int AREA[22][MAX * MAX][MAX * MAX];

void makeArea(int k)
{
	cost[k] = k * k + (k - 1) * (k - 1);

	for (int r = 1; r <= k; r++)
		for (int c = k + 1 - r; c <= k + r - 1; c++)
			AREA[k][r][c] = 1;


	for (int r = k + 1; r <= 2 * k - 1; r++)
		for (int c = r - k + 1; c <= 3 * k - r - 1; c++)
			AREA[k][r][c] = 1;
}

int main(void)
{
	for (int i = 1; i <= 21; i++) makeArea(i);
    
	...
}

---

scan 함수는 운영 영역 K에 대해 존재하는 집의 개수를 모두 찾는 함수이다.

AREA의 영역에 1을 표시하였으므로, 범위를 벗어나지 않는 MAP을 곱해서 sum에 더하면 된다.

int scan(int sr, int sc)
{
	int sum = 0;
	for (int r = 1; r <= 2 * K - 1; r++)
	{
		for (int c = 1; c <= 2 * K - 1; c++)
		{
			if (sr + r < 1 || sr + r > N || sc + c < 1 || sc + c > N) continue;
			sum += MAP[sr + r][sc + c] * AREA[K][r][c];
		}
	}

	return sum;
}

 

scan 함수까지 만들었기 때문에 K를 점점 줄여나가면서 maxAreaNum을 갱신하면 된다.

갱신 할 때, 손해를 보지 않아야 하므로 집의 수 * M - cost[K]가 0보다 큰 경우만 갱신한다.

input();

int areaNum, maxAreaNum;

areaNum = maxAreaNum = 0;
while (maxAreaNum <= 0)
{
	for (int r = 1; r <= N + K + 1; r++)
	{
		for (int c = 1; c <= N + K + 1; c++)
		{
			areaNum = scan(r - K - 1, c - K - 1);

			if (areaNum * M - cost[K] >= 0)
			{
				if (maxAreaNum < areaNum) maxAreaNum = areaNum;
			}
		}
	}

	K--;
}

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

 

전체 코드는 아래와 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T, N, M;
int MAP[MAX][MAX];
int AREA[22][MAX * MAX][MAX * MAX];

int K;
int cost[22];

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	K = N + 1;
}

void makeArea(int k)
{
	cost[k] = k * k + (k - 1) * (k - 1);

	for (int r = 1; r <= k; r++)
		for (int c = k + 1 - r; c <= k + r - 1; c++)
			AREA[k][r][c] = 1;


	for (int r = k + 1; r <= 2 * k - 1; r++)
		for (int c = r - k + 1; c <= 3 * k - r - 1; c++)
			AREA[k][r][c] = 1;
}

int scan(int sr, int sc)
{
	int sum = 0;
	for (int r = 1; r <= 2 * K - 1; r++)
	{
		for (int c = 1; c <= 2 * K - 1; c++)
		{
			if (sr + r < 1 || sr + r > N || sc + c < 1 || sc + c > N) continue;
			sum += MAP[sr + r][sc + c] * AREA[K][r][c];
		}
	}

	return sum;
}

int main(void)
{
	for (int i = 1; i <= 21; i++) makeArea(i);

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

		int areaNum, maxAreaNum;

		areaNum = maxAreaNum = 0;
		while (maxAreaNum <= 0)
		{
			for (int r = 1; r <= N + K + 1; r++)
			{
				for (int c = 1; c <= N + K + 1; c++)
				{
					areaNum = scan(r - K - 1, c - K - 1);

					if (areaNum * M - cost[K] >= 0)
					{
						if (maxAreaNum < areaNum) maxAreaNum = areaNum;
					}
				}
			}

			K--;
		}

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

	return 0;
}