💡 브루트포스 알고리즘/구현/시뮬레이션
Memory 2024KB Time 4ms Code Length 2499B
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
#include<iostream>
using namespace std;
int N;
int map[21][21];
int holesum = 0;
// 직사각형을 찾고 나머지 부분 더해주기
void init() {
cin >> N;
holesum = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
holesum += map[i][j];
}
}
}
int sector1(int x, int y, int d1) {
int cnt = 0;
for (int r = 1; r < x + d1; r++) {
if (r < x) { // r < x 일때
for (int c = 1; c <= y; c++) {
cnt += map[r][c];
}
}
else { // r >= x 일때
for (int c = 1; c <= y - 1 - (r - x); c++) {
cnt += map[r][c];
}
}
}
return cnt;
}
int sector2(int x, int y, int d2) {
int cnt = 0;
for (int c = y + 1; c <= N; c++) {
if (c > y + d2) {
for (int r = 1; r <= x + d2; r++) {
cnt += map[r][c];
}
}
else {
for (int r = 1; r <= x + d2 - 1 - (y + d2 - c); r++) {
cnt += map[r][c];
}
}
}
return cnt;
}
int sector3(int x, int y, int d1, int d2) {
int cnt = 0;
for (int r = x + d1; r <= N; r++) {
if (r >= x + d1 + d2) {
for (int c = 1; c < y - d1 + d2; c++) {
cnt += map[r][c];
}
}
else {
for (int c = 1; c < y - d1 + d2 - ((x + d1 + d2) - r); c++) {
cnt += map[r][c];
}
}
}
return cnt;
}
int sector4(int x, int y, int d1, int d2) {
int cnt = 0;
for (int r = x + d2 + 1; r <= N; r++) {
if (r > x + d1 + d2) {
for (int c = y - d1 + d2; c <= N; c++) {
cnt += map[r][c];
}
}
else {
for (int c = y - d1 + d2 + 1 + ((x + d1 + d2) - r); c <= N; c++) {
cnt += map[r][c];
}
}
}
return cnt;
}
int getMax(int num[5]) {
int MaxV = 0;
for (int i = 0; i < 5; i++) {
if (num[i] > MaxV) MaxV = num[i];
}
return MaxV;
}
int getMin(int num[5]) {
int MinV = 1e9;
for (int i = 0; i < 5; i++) {
if (num[i] < MinV) MinV = num[i];
}
return MinV;
}
int solve() {// x, y, d1, d2 선택하기
int result = 1e9;
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
for (int d1 = 1; d1 <= N - 2; d1++) {
for (int d2 = 1; d2 <= N - 2; d2++) {
if (x + d1 + d2 > N || 1 > y - d1 || y + d2 > N) continue;
int sec[5] = { 0 };
sec[0] = sector1(x, y, d1);
sec[1] = sector2(x, y, d2);
sec[2] = sector3(x, y, d1, d2);
sec[3] = sector4(x, y, d1, d2);
sec[4] = holesum - sec[0] - sec[1] - sec[2] - sec[3];
int maxV = getMax(sec);
int minV = getMin(sec);
int tmp = maxV - minV;
if (result > tmp) result = tmp;
}
}
}
}
return result;
}
int main() {
init();
cout << solve() << endl;
}
이 코드는 N*N 크기의 지도 정보를 입력받고, 주어진 조건에 따라 직사각형을 선택하여 해당 직사각형을 제외한 나머지 부분의 값을 계산하는 프로그램이다.
init 함수에서는 N*N 크기의 지도 정보를 입력받고, holesum 변수에 모든 지도의 값을 더해준다.
sector1, sector2, sector3, sector4 함수는 각각 주어진 조건에 따라 선택한 직사각형의 부분을 계산하는 함수이다.
getMax, getMin 함수는 배열에서 최댓값과 최솟값을 찾는 함수이다.
solve 함수에서는 가능한 모든 직사각형을 선택하고, 각각의 부분을 계산하여 최대값과 최소값을 구한 후, 그 차이를 계산한다. 그리고 이 중에서 최소값을 찾아 결과로 반환한다.
main 함수에서는 init 함수를 호출하여 지도 정보를 입력받고, solve 함수를 호출하여 결과를 출력한다.
