[코드트리] 종전 (삼성 SW 역량테스트 2019 하반기 오전 1번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/war-finish

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

 

종전 문제 풀이는 BOJ 17779 : 게리맨더링 2와 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T;
int N;
int MAP[MAX][MAX];
int minAnswer;

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

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

void output(int map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void calculate(int sr, int sc, int d1, int d2)
{
	int area[MAX][MAX] = { 0 };
	int sum[6] = { 0 };
	int start, end, left, right;
	int min, max;

	start = end = sc;
	left = -1, right = 1;
	for (int r = sr; r <= sr + d1 + d2; r++)
	{
		for (int c = start; c <= end; c++) area[r][c] = 5;

		start += left;
		end += right;

		if (start == sc - d1) left = 1;
		if (end == sc + d2) right = -1;
	}

	// 1
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (area[r][c] == 5) break;
			if ((1 <= r && r < sr + d1) && (1 <= c && c <= sc)) area[r][c] = 1;
		}
	}

	// 2
	for (int r = 1; r <= N; r++)
	{
		for (int c = sc; c <= N; c++)
		{
			if (area[r][c] == 5) continue;
			if ((1 <= r && r <= sr + d2) && (sc < c && c <= N)) area[r][c] = 2;
		}
	}

	// 3
	for (int r = sr; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (area[r][c] == 5) break;
			if ((sr + d1 <= r && r <= N) && (1 <= c && c < sc - d1 + d2)) area[r][c] = 3;
		}
	}

	// 4
	for (int r = sr; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (area[r][c] == 5) continue;
			if ((sr + d2 < r && r <= N) && (sc - d1 + d2 <= c && c <= N)) area[r][c] = 4;
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			sum[area[r][c]] += MAP[r][c];

	//for debug
	//for (int r = 1; r <= N; r++)
	//{
	//	for (int c = 1; c <= N; c++)
	//		printf("%d ", area[r][c]);
	//	putchar('\n');

	//}
	//putchar('\n');

	min = 0x7fff0000;
	max = -0x7fff0000;

	for (int i = 1; i <= 5; i++)
	{
		if (sum[i] < min) min = sum[i];
		if (sum[i] > max) max = sum[i];
	}

	if (max - min < minAnswer) minAnswer = max - min;
}

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

		for (int r = 1; r <= N - 2; r++)
		{
			for (int c = 2; c <= N - 1; c++)
			{
				for (int d1 = 1; ; d1++)
				{
					if (MAP[r + d1][c - d1] == -1) break;

					for (int d2 = 1; ; d2++)
					{
						if (MAP[r + d2][c + d2] == -1 || MAP[r + d1 + d2][c + d2 - d1] == -1) break;

						calculate(r, c, d1, d2);
					}
				}
			}
		}

		printf("%d\n", minAnswer);
	}

	return 0;
}