## SW 역량테스트 - [백준] 게리맨더링 2 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

### SW 역량테스트 - [백준] 게리맨더링 2 문제 풀이/해답/코드 (C++ / JAVA)

머니덕 2020. 10. 15. 23:52

## SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

### 해답 코드 :

``````#include <iostream>
#include <vector>

using namespace std;

typedef struct pos {

int row;
int col;

}pos;

int st_r, st_c, d1, d2;
int N;

int map[20][20];
// mark vote district
int vote[20][20];
// number of people in the district
int popul[6];

int ans;

// 0 : Left, 1 : Up, 2 : Right, 3 : Down
pos vertex[4];

bool isRange(int r, int c) {

if (r < 0 || r >= N || c < 0 || c >= N) {
return false;
}
else {
return true;
}

}

// paint area 1
void paint_1() {
for (int i = 0; i < vertex[0].row; i++) {
for (int j = 0; j <= vertex[1].col; j++) {
if (vote[i][j] == 5) {
break;
}
vote[i][j] = 1;
}
}
}

// paint area 2
void paint_2() {
for (int i = 0; i <= vertex[2].row; i++) {
for (int j = N-1; j > vertex[1].col; j--) {
if (vote[i][j] == 5) {
break;
}
vote[i][j] = 2;
}
}
}

// paint area 3
void paint_3() {
for (int i = vertex[0].row; i < N; i++) {
for (int j = 0; j < vertex[3].col; j++) {
if (vote[i][j] == 5) {
break;
}
vote[i][j] = 3;
}
}
}

// paint area 4
void paint_4() {
for (int i = vertex[2].row+1; i < N; i++) {
for (int j = N-1; j >= vertex[3].col; j--) {
if (vote[i][j] == 5) {
break;
}
vote[i][j] = 4;
}
}
}

// paint line of area 5 and fill 0 with 5
void paint() {

// paint lines of area 5
// line 1
for (int i = 0; i < d1; i++) {
vote[vertex[0].row-i][vertex[0].col+i] = 5;
}

// line 2
for (int i = 0; i < d2; i++) {
vote[vertex[1].row+i][vertex[1].col+i] = 5;
}
// line 3
for (int i = 0; i < d1; i++) {
vote[vertex[2].row + i][vertex[2].col - i] = 5;
}
// line 4
for (int i = 0; i < d2; i++) {
vote[vertex[3].row - i][vertex[3].col - i] = 5;
}

paint_1();
paint_2();
paint_3();
paint_4();

// paint 0 area to 5
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (vote[i][j] == 0) {
vote[i][j] = 5;
}
}
}

}

void count() {

int min_val = INT16_MAX, max_val = INT16_MIN;

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
popul[vote[i][j]] += map[i][j];
}
}

// update difference
for (int i = 1; i < 6; i++) {
min_val = min(min_val, popul[i]);
max_val = max(max_val, popul[i]);
}

ans = min(ans, max_val - min_val);

}

// paint area 5 and call divde_1 ~ 4
void divide() {

// pick st_r, st_c
for (int i = 1; i < N - 1; i++) {
for (int j = 0; j < N - 2; j++) {

// pick d1, d2. k -> d1, l -> d2
for (int k = 1; k < N - 1; k++) {
for (int l = 1; l < N - 1; l++) {

// if in range, do paint map
if ((j + k + l) < N && (i-k) >= 0 && (i+l) < N) {
d1 = k;
d2 = l;

// 0 : Left, 1 : Up, 2 : Right, 3 : Down
vertex[0] = { i, j };
vertex[1] = { i - d1, j + d1 };
vertex[2] = { i - d1 + d2, j + d1 + d2 };
vertex[3] = { i + d2, j + d2 };

paint();

// count number of people of each district
// use vote[][]
count();

// initialize vote[][] and popul
fill(&vote[0][0], &vote[19][20], 0);
fill_n(&popul[0], 6, 0);

}
else {
continue;
}

}
}

}
}

}

int main() {

cin >> N;
ans = INT32_MAX;

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}

divide();

cout << ans << endl;

}
``````

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

#### 'Data Structures, Algorithm > SW 역량테스트' 카테고리의 다른 글

 SW 역량테스트 - [백준] 원판 돌리기 문제 풀이/해답/코드 (C++ / JAVA)  (0) 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15