반응형
https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름
www.acmicpc.net
처음 접근법
: 5구역을 먼저 계산하고 1~4구역을 계산
① 5구역 계산하면서 visited 체크
② 1~4구역을 문제에서 주어진 수식대로 범위를 지정하여 계산.
for문을 돌리면서 visited 처리가 된 것은 5구역에 포함되는 부분이므로, 각 구역 계산 시 포함시키지 않음
문제점
1~4구역 나누는 것은 문제에 주어진 수식을 참고하여 코드를 작성했지만,
5구역 나누는 법은 도무지 생각이 나지 않았다...
두 번째 접근법 (블로그 참고)
: 1~4구역을 먼저 계산하고 5구역을 계산
① 1~4구역 계산 시, if 문에서 5구역을 걸러내는 조건을 이용해서 5구역 필터링.
② 전체 영억 - (1~4구역) 으로 5구역 계산
문제점
5구역을 걸러내는 조건이 아주 까다로웠다...
그림을 그려봐도, 코드를 계속 읽어봐도 이해가 안됐다.
무엇보다 비슷한 유형의 문제를 풀 때, 이 방법대로 구현할 자신이 없었다.
세 번째 접근법 (유튜브 참고): https://youtu.be/fAs85oVcu1g
: 5구역의 경계를 설정하고, 1~4구역 계산 시 필터링
① 문제에서 주어진 5구역 경계 수식을 참고하여 5구역 경계 설정
② 1~4구역 계산 시 5구역의 경계를 만나면 다음 행으로 넘어감
해결
이 영상 보자마자 바로 방법을 깨달았다.
단순하게 5구역의 경계만 설정함으로써 간단하게 1~4구역을 계산할 수 있었다.
복잡하게 5구역을 먼저 계산할 필요도, 1~4구역 계산 시 5구역 필터링을 어렵게 할 필요도 없는 것이다.
5구역의 경계를 설정하는 수식은 아주 간단하다. 문제에 있는 조건을 그대로 이용하면 된다.
문제에서 주어진 5구역의 경계
5구역의 경계를 표시하는 소스코드
|
1
2
3
4
5
6
7
8
9
|
// 5구역 경계 설정
for (int i = 0; i <= d1; i++) {
border[x + i][y - i] = 5; // 5-1 경계 (x, y), (x+1, y-1), ..., (x+d1, y-d1)
border[x + d2 + i][y + d2 - i] = 5; // 5-4 경계 (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
}
for (int i = 0; i <= d2; i++) {
border[x + i][y + i] = 5; // 5-2 경계 (x, y), (x+1, y+1), ..., (x+d2, y+d2)
border[x + d1 + i][y - d1 + i] = 5; // 5-3 경계 (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
}
|
cs |
1~4구역 계산도 마찬가지로 문제에 주어진 수식을 활용하여 쉽게 수행할 수 있다.
문제에서 주어진 1~4구역의 범위
1~4구역 계산하는 소스코드
|
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
|
// 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
for (int i = 1; i < x+d1; i++) {
for (int j = 1; j <= y; j++) {
if (border[i][j] == 5) break;
area[1] += arr[i][j];
}
}
// 2번 선거구 : 1 ≤ r ≤ x + d2, y < c ≤ N
for (int i = 1; i <= x + d2; i++) {
for (int j = n; j > y; j--) {
if (border[i][j] == 5) break;
area[2] += arr[i][j];
}
}
// 3번 선거구 : x + d1 ≤ r ≤ N, 1 ≤ c < y - d1 + d2
for (int i = x+d1; i <= n; i++) {
for (int j = 1; j < y-d1+d2; j++) {
if (border[i][j] == 5) break;
area[3] += arr[i][j];
}
}
// 4번 선거구 : x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
for (int i = x + d2+1; i <= n; i++) {
for (int j = n; j >= y-d1+d2; j--) {
if (border[i][j] == 5) break;
area[4] += arr[i][j];
}
}
// 5번 선거구
area[5] = total;
rep(i, 4)
area[5] -= area[i];
|
cs |
진행 과정
0123
전체 소스코드
|
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
|
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, arr[21][21], area[6], border[21][21];
int max_val, min_val, ans = 1e9, total;
void input();
void init();
bool isValidArea(int x, int y, int d1, int d2); // 범위 검사
void getArea(int x, int y, int d1, int d2); // 범위 계산
// 1. (x, y), d1, d2 정하기
// 2. 구역 별 인구수 계산
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
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++) {
init();
if (isValidArea(x, y, d1, d2)) {
getArea(x, y, d1, d2);
ans = min(ans, max_val - min_val);
}
}
}
}
}
cout << ans;
}
bool isValidArea(int x, int y, int d1, int d2) {
if (x<1 || x>n || y<1 || y>n) return 0; // 상: (x,y)
if (x + d1 + d2<1 || x + d1 + d2>n || y - d1 + d2<1 || y - d1 + d2>n) return 0; // 하: (x+d1+d2, y-d1+d2)
if (x + d1<1 || x + d1>n || y - d1<1 || y - d1>n) return 0; // 좌: (x+d1, y-d1)
if (x + d2<1 || x + d2>n || y + d2<1 || y + d2>n) return 0; // 우: (x+d2, y+d2)
return 1;
}
// 범위 계산
void getArea(int x, int y, int d1, int d2) {
// 5구역 경계 설정
for (int i = 0; i <= d1; i++) {
border[x + i][y - i] = 5; // 5-1 경계 (x, y), (x+1, y-1), ..., (x+d1, y-d1)
border[x + d2 + i][y + d2 - i] = 5; // 5-4 경계 (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
}
for (int i = 0; i <= d2; i++) {
border[x + i][y + i] = 5; // 5-2 경계 (x, y), (x+1, y+1), ..., (x+d2, y+d2)
border[x + d1 + i][y - d1 + i] = 5; // 5-3 경계 (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
}
// 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
for (int i = 1; i < x+d1; i++) {
for (int j = 1; j <= y; j++) {
if (border[i][j] == 5) break;
area[1] += arr[i][j];
}
}
// 2번 선거구 : 1 ≤ r ≤ x + d2, y < c ≤ N
for (int i = 1; i <= x + d2; i++) {
for (int j = n; j > y; j--) {
if (border[i][j] == 5) break;
area[2] += arr[i][j];
}
}
// 3번 선거구 : x + d1 ≤ r ≤ N, 1 ≤ c < y - d1 + d2
for (int i = x+d1; i <= n; i++) {
for (int j = 1; j < y-d1+d2; j++) {
if (border[i][j] == 5) break;
area[3] += arr[i][j];
}
}
// 4번 선거구 : x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
for (int i = x + d2+1; i <= n; i++) {
for (int j = n; j >= y-d1+d2; j--) {
if (border[i][j] == 5) break;
area[4] += arr[i][j];
}
}
// 5번 선거구
area[5] = total;
rep(i, 4)
area[5] -= area[i];
rep(i, 5) {
max_val = max(max_val, area[i]);
min_val = min(min_val, area[i]);
}
}
void input() {
cin >> n;
rep(i, n) {
rep(j, n) {
cin >> arr[i][j];
total += arr[i][j];
}
}
}
void init() {
memset(area, 0, sizeof(area));
memset(border, 0, sizeof(border));
max_val = -1;
min_val = 1e9;
}
|
cs |
반응형
'백준 > 삼성기출' 카테고리의 다른 글
| 백준 17837 [4%에서 틀렸습니다.] (0) | 2021.08.08 |
|---|---|
| 백준 17142 (0) | 2021.08.04 |
| 백준 17143 (0) | 2021.07.19 |
| 백준 5373 [복습필수] (0) | 2021.04.30 |
| 백준 16234 (0) | 2021.04.30 |