반응형
https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다
www.acmicpc.net
|
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
|
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int N;
int ARR[21][21];
int Label[21][21];
bool isPossible(int y,int x,int d1,int d2){
if(y-d1 < 1) return false;
if(y+d2 > N) return false;
if(x+d1+d2 > N) return false;
return true;
}
int Difference_sum(int y,int x,int d1,int d2){
int Posy[4] = {y,y-d1,y-d1+d2,y+d2};
int Posx[4] = {x,x+d1,x+d1+d2,x+d2};
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
Label[i][j] = 5;
}
}
int sub=0;
//1번 칠하기
for(int i=1; i<Posy[0];++i){
if(Posy[1]<= i) ++sub;
for(int j=1;j<=Posx[1] - sub;++j){
Label[i][j] = 1;
}
}
sub=0;
//2번 칠하기
for(int i=0;i<=Posy[2];++i){
if(Posy[1]<i) ++sub;
for(int j=Posx[1]+1 +sub ; j<=N;++j){
Label[i][j] = 2;
}
}
//3번 칠하기
sub=0;
for(int i=N;i>=Posy[0];--i){
if(i<Posy[3])++sub;
for(int j=0;j<Posx[3] - sub;++j){
Label[i][j] = 3;
}
}
//4번 칠하기
sub=0;
for(int i=N;i>Posy[2];--i){
if(i<=Posy[3]) ++sub;
for(int j=N;j>=Posx[3]+sub;--j){
Label[i][j] =4;
}
}
int sum[6] ={0,};
for(int i =1;i<=N;++i){
for(int j=1;j<=N;++j){
sum[Label[i][j]] += ARR[i][j];
}
}
int maxv = ~0x7f7f7f7f + 1;
int minv = 0x7f7f7f7f;
for(int i=1;i<=5;++i){
maxv = max(maxv,sum[i]);
minv = min(minv,sum[i]);
}
return maxv - minv;
}
int Solve(){
int MIN_VALUE = 987654321;
for(int y=1;y<=N;++y){
for(int x=1;x<=N;++x){
for(int d1=1;d1<N;++d1){
if(!isPossible(y,x,d1,1)) break;
for(int d2=1;d2<N;++d2){
if(isPossible(y,x,d1,d2)){
//구역별 최소값 구하기.
MIN_VALUE = min(MIN_VALUE, Difference_sum(y,x,d1,d2));
}
}
}
}
}
return MIN_VALUE;
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>N;
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
cin>>ARR[i][j];
}
}
cout<<Solve();
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'ProgramSoliving' 카테고리의 다른 글
| 백준 : 2565 (0) | 2020.01.12 |
|---|---|
| 백준 : 2869 (0) | 2020.01.12 |
| 백준 : 14891 (0) | 2020.01.12 |
| 백준 : 14890 (0) | 2020.01.12 |
| 백준 : 16234 * (0) | 2020.01.11 |