https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도
www.acmicpc.net
진짜 알고리즘은 하나도 없고
구현 뿐이다. 구현을 위한 문제이다.
가장 중요한 건 그려봐야 한다는 것이다.
D1은 현재 좌표에서 대각선 왼쪽 아래로 얼마만큼 움직일 수 있냐? 를 결정
D2의 경우 쉽게 생각해서 현재좌표에서 대각선 오른쪽 아래로 얼마만큼 움직일 수 있냐 ? 를 결정
그려보면 알 수 있다.
그리고 이중 for문을 돌리면 d1, d2 범위를 정하고 거기서
label을 붙이고
calculate를 해서 최소값을 갱신하면 된다.
<소스 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans = 987654321;
int map[25][25];
int label[25][25];
struct info
{
int x;
int y;
};
info pos[4];
bool dekiru(int x, int y, int d1, int d2)
{
if (x + d1 >= n || y - d1 < 0) return false;
if (x + d2 >= n || y + d2 >= n) return false;
if (x + d1 + d2 >= n || y - d1 + d2 >= n) return false;
if (x + d2 + d1 >= n || y + d2 - d1 < 0) return false;
return true;
}
void calculate()
{
int hap[6] = { 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
hap[label[i][j]] = hap[label[i][j]] + map[i][j];
}
sort(hap, hap + 6);
int diff = hap[5] - hap[1];
ans = min(ans, diff);
}
void labeling(int a, int b, int c, int d)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
label[i][j] = 5;
}
int subarea = 0;
for (int i = 0; i < pos[1].x; i++)
{
if (i >= pos[0].x) subarea++;
for (int j = 0; j <= pos[0].y - subarea; j++)
label[i][j] = 1;
}
int plusarea = 0;
for (int i = 0; i <= pos[2].x; i++)
{
if (i > pos[0].x) plusarea++;
for (int j = pos[0].y + 1 + plusarea; j < n; j++)
label[i][j] = 2;
}
subarea = 0;
for (int i = n - 1; i >= pos[1].x; i--)
{
if (i < pos[3].x) subarea++;
for (int j = 0; j < pos[3].y - subarea; j++)
label[i][j] = 3;
}
plusarea = 0;
for (int i = n - 1; i > pos[2].x; i--)
{
if (i <= pos[3].x) plusarea++;
for (int j = pos[3].y + plusarea; j < n; j++)
label[i][j] = 4;
}
calculate();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> map[i][j];
}
for (int i = 0; i < n; i++)
{
for (int j = 1; j < n; j++)
{
for (int d1 = 1; d1 <= j; d1++)
{
for (int d2 = 1; d2 < n - j; d2++)
{
if (dekiru(i, j, d1, d2) == true)
{
pos[0].x = i; pos[0].y = j;
pos[1].x = i + d1; pos[1].y = j - d1;
pos[2].x = i + d2; pos[2].y = j + d2;
pos[3].x = i + d1 + d2; pos[3].y = j - d1 + d2;
labeling(i, j, d1, d2);
}
}
}
}
}
cout << ans << '\n';
return 0;
}
|
cs |
'시뮬레이션과 구현' 카테고리의 다른 글
| 미세먼지 안녕! (0) | 2023.09.27 |
|---|---|
| 이차원 배열과 연산 (0) | 2023.09.26 |
| 연구소 3 (0) | 2023.09.24 |
| 아기 상어 (0) | 2023.09.23 |
| 마법사 상어와 파이어볼 + 비바라기 (1) | 2023.09.21 |
