[백준] 17779 게리맨더링 2 (C++)

백준 17779 게리맨더링 2

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

지문에서 제시된 수식 조건만 잘 사용하여 1번 ~ 5번 선거구까지 정확하게 나누면 풀리는 문제였다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

위 조건을 사용하여 선거구를 나누고 각 선거구의 max, min값을 구해 차이의 가장 작은 값을 리턴하면 된다.

3. 코드

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int n, sum;
int map[101][101];
int solve(int x, int y, int d1, int d2)
{
	//경계선과 경계선안의 영역은 5번 선거구이므로 
	//5번 선거구를 담을 임시 배열 선언
	int tmp[21][21] = { 0, };
	tmp[x][y] = 5;

	//경계선에 해당하는 영역에 5번 선거구 표시
	/* (x+d1, y-d1), (x+d2+d1, y+d2-d1) */
	for (int i = 1; i <= d1; ++i)
	{
		tmp[x + i][y - i] = 5;
		tmp[x + d2 + i][y + d2 - i] = 5;
	}
	/* (x+d2, y+d2), (x+d1+d2, y-d1+d2) */
	for (int i = 1; i <= d2; ++i)
	{
		tmp[x + i][y + i] = 5;
		tmp[x + d1 + i][y - d1 + i] = 5;
	}

	//1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
	int one = 0;
	for (int r = 1; r < x + d1; ++r)
	{
		for (int c = 1; c <= y; ++c)
		{
			if (tmp[r][c] == 5)
				break;
			one += map[r][c];
		}
	}
	//2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
	int two = 0;
	for (int r = 1; r <= x + d2; ++r)
	{
		for (int c = n; c > y; --c)
		{
			if (tmp[r][c] == 5)
				break;
			two += map[r][c];
		}
	}
	//3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
	int three = 0;
	for (int r = x + d1; r <= n; ++r)
	{
		for (int c = 1; c < y - d1 + d2; ++c)
		{
			if (tmp[r][c] == 5)
				break;
			three += map[r][c];
		}
	}
	//4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
	int four = 0;
	for (int r = x + d2 + 1; r <= n; ++r)
	{
		for (int c = n; c >= y - d1 + d2; --c)
		{
			if (tmp[r][c] == 5)
				break;
			four += map[r][c];
		}
	}
	//5번 선거구: 전체에서 나머지 인구를 빼면 됨
	int five = sum - (one + two + three + four);
	//인구가 가장 많은 선거구와 적은 선거구의 인구수를 구함
	int maxi = max(one, max(two, max(three, max(four, five))));
	int mini = min(one, min(two, min(three, min(four, five))));
	//인구 차이 리턴
	return (maxi - mini);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	//최소값을 구하기 위한 변수
	int ans = 987654321;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			//map을 입력받으면서 전체 인구수를 구함
			cin >> map[i][j];
			sum += map[i][j];
		}
	}
	/* 지문에서 주어진 d1, d2의 조건에 따라 경계선을 구함
	(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 
						1 ≤ y-d1 < y < y+d2 ≤ N) */
	for (int x = 1; x <= n; ++x)
	{
		for (int y = 1; y <= n; ++y)
		{
			for (int d1 = 1; d1 <= n; ++d1)
			{
				for (int d2 = 1; d2 <= n; ++d2)
				{
					if (x + d1 + d2 > n)
						continue;
					if (y - d1 < 1)
						continue;
					if (y + d2 > n)
						continue;
					//조건에 만족하는 경우 solve함수로 넘겨주고
					//인구 차이의 최소값을 ans에 업데이트 시킴
					ans = min(ans, solve(x, y, d1, d2));
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

4. 시간 복잡도

시뮬레이션 문제이므로 별도의 알고리즘을 사용하지 않고 풀었다.

4중 for문을 돌리면서 예외처리를 하여 조건에 만족하는 경우만 solve함수를 탄다. 또 n의 최댓값이 21이므로 1초 내에 구현 가능하다.

5. 결과