백준 17779 게리맨더링2

#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
#define NS 21
int N;
int A[NS][NS];
int chk[NS][NS];

int flag;
struct Data {
	int y, x;
};
void areaWrite(int y, int x, int d1, int d2) {// 성공 문제
	flag = 0;
	memset(chk, 0, sizeof(chk));
	vector<Data>v;
	vector<Data>v1;
	//one
	for (int i = y, j = x; i <= y + d1 && j >= x - d1; i++, j--) {
		if (i<1 || i>N || j<1 || j>N) {
			flag = 1; return;
		}
		v.push_back({ i,j });
		chk[i][j] = 5;
	}
	//three
	for (int i = y + d1 + 1, j = x - d1 + 1; i <= y + d1 + d2 && j <= x - d1 + d2; i++, j++) {
		if (i<1 || i>N || j<1 || j>N) {
			flag = 1; return;
		}
		v.push_back({ i,j });
		chk[i][j] = 5;
	}
	if (flag == 1)return;
	if (flag == 1)return;
	//two
	for (int i = y, j = x; i <= y + d2 && j <= x + d2; i++, j++) {
		if (i<1 || i>N || j<1 || j>N) {
			flag = 1; return;
		}
		v1.push_back({ i,j });
		chk[i][j] = 5;
	}
	if (flag == 1)return;

	//four
	for (int i = y + d2 + 1, j = x + d2 - 1; i <= y + d2 + d1 && j >= x + d2 - d1; i++, j--) {
		if (i<1 || i>N || j<1 || j>N) {
			flag = 1; return;
		}
		v1.push_back({ i,j });
		chk[i][j] = 5;
	}

	for (int i = 0; i < v.size(); i++) {
		for (int ii = v[i].y; ii <= v1[i].y; ii++) {
			for (int jj = v[i].x; jj <= v1[i].x; jj++) {
				chk[ii][jj] = 5;
			}
		}
	}
}
int flag2 = 0;
void fourArea(int y, int x, int d1, int d2) {
	flag2 = 0;
	for (int i = 1; i < y + d1; i++) {
		for (int j = 1; j <= x; j++) {
			if (chk[i][j] == 0)
				chk[i][j] = 1;
			if (flag2 == 0)
				flag2++;
		}
	}
	for (int i = 1; i <= y + d2; i++) {
		for (int j = x + 1; j <= N; j++) {
			if (chk[i][j] == 0)
				chk[i][j] = 2;
			if (flag2 == 1)
				flag2++;
		}
	}
	for (int i = y + d1; i <= N; i++) {
		for (int j = 1; j < x - d1 + d2; j++) {
			if (chk[i][j] == 0)
				chk[i][j] = 3;
			if (flag2 == 2)
				flag2++;
		}
	}
	for (int i = y + d2 + 1; i <= N; i++) {
		for (int j = x - d1 + d2; j <= N; j++) {
			if (chk[i][j] == 0)
				chk[i][j] = 4;
			if (flag2 == 3)
				flag2++;
		}
	}
}void search() {
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			if (chk[y][x] == 0) {

			}
		}
	}
}
int Min = 0x7fffffff;
void sparateArea() {

	for (int d1 = 1; d1 <= N; d1++) {
		for (int d2 = 1; d2 <= N; d2++) {
			for (int y = 1; y <= N; y++) {
				for (int x = 1; x <= N; x++) {
					areaWrite(y, x, d1, d2);
					if (flag == 1)continue;
					search();
					fourArea(y, x, d1, d2);
					if (flag2 != 4)continue;
					int sum[6] = { 0, };
					for (int i = 1; i <= N; i++) {
						for (int j = 1; j <= N; j++) {
							sum[chk[i][j]] += A[i][j];
							// printf("%2d", chk[i][j]);
						}
						//  printf("\n");
					}
					// printf("\n");
					int max = 0x80000000; int min = 0x7fffffff;

					for (int m = 1; m <= 5; m++) {
						if (max < sum[m])max = sum[m];
						if (min > sum[m])min = sum[m];
					}
					if (Min > max - min)Min = max - min;
				}
			}
		}
	}
}
void init() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	sparateArea();
	cout << Min << endl;
}
int main(void) {
	init();
	return 0;
}

진짜 그냥 있는 그대로 구현한 문제 였습니다. 

 

설계는 저렇게 하려고했지만 결국은 다르게 구현했던것은 함정이네요 ㅋㅋ 그래도 저렇게 처음에 결과가왜 저렇게 나오는지 확인하고 하니까 중간에 설계를 바꾸더라도 쉽게 풀수 있었습니다.

 

간단히 설명하자면 이문제는 자체적으로 범위를 다 가르쳐주기때문에 그냥 d1 d2 y x 이렇게 전체 포문 즉 사중 포문을

돌게하면서 5의 자치구를 형성할 수 있는걸 찾아서 5로 채우고

나머지 1 2 3 4의 범위에 맞게 0인 공간에 1 2 3 4 를 새기고 그상태에서 5개의 자치구가 형성되었는지 확인이되면

계산해서 최대 에 최소를 빼고 그것에 최소를 구하면 되는 문제로 그냥 구현을 하시면 되긴 해서 그렇게 풀었습니다.

물론 다른 방법도 있겠지만 시간을 재고 풀다보니 쉽게 생각할 수있는 방법으로 구현했네요

그럼 오늘은 여기까지입니다. 그럼 이만 ..