게리맨더링2
문제링크
https://www.acmicpc.net/problem/17779
처음에 시간초과 나와서 굉장히 당황한 문제.. 잘못된 알고리즘 이었다..!!!!
먼저 5구역을 경계선 범위를 기준으로 체크해준 뒤
1,2,3,4 구역이 각각 5구역을 만났을때 break 해서 다음행을 실행하는 방식으로
구역을 나누었다.
그리고 1,2,3,4 각 구역을 탐색할때 각 구역의 합을 구했고 5구역의 경우 경계선만 체크 되기 때문에
전체합에서 1,2,3,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
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
import sys
sys.stdin = open("input.txt",'r')
n = int(input())
board = [[int(x) for x in input().split()]for _ in range(n)]
total = 0
for i in range(n):
for j in range(n):
total += board[i][j]
# 먼저 경계선을 기준으로 5구역을 NEW_BOARD 에 할당한뒤
# 나머지 구역이 new_board[i][j] == 5 일 경우를 피해서 각각 구역을 할당해줬다
# 구역을 구하면서 각각 구역의 총합을 구했고
# 5구역은 총합에서 1,2,3,4 의 구역 합을 빼는 방법으로 진행하였다.
# 정해진 범위의 구역도 나누고 합까지 구하기
def board_sum(x,y,d1,d2):
new_board = [[0]*n for _ in range(n)]
b_1 = 0
b_2 = 0
b_3 = 0
b_4 = 0
b_min = 9999999999999999999999
b_max = 0
# 5번 구역
for i in range(d1+1):
new_board[x+i-1][y-i-1] = 5
for i in range(d2+1):
new_board[x+i-1][y+i-1] = 5
for i in range(d2+1):
new_board[x+d1+i-1][y-d1+i-1] = 5
for i in range(d1+1):
new_board[x+d2+i-1][y+d2-i-1] = 5
# 1번 구역
for i in range(1,x+d1):
for j in range(1,y+1):
if new_board[i-1][j-1]==5:
break
new_board[i-1][j-1] = 1
b_1 += board[i-1][j-1]
if b_1 > b_max:
b_max = b_1
if b_1 < b_min:
b_min = b_1
#2번 구역
# 열이 거꾸로 시작해야 5의 경계선을 마지막으로 만나기 때문에 j 의 range를 -1 씩
# 해주도록 range를 설정하였다.
for i in range(1,x+d2+1):
for j in range(n,y,-1):
if new_board[i-1][j-1]==5:
break
new_board[i-1][j-1] = 2
b_2 += board[i-1][j-1]
if b_2 > b_max:
b_max = b_2
if b_2 < b_min:
b_min = b_2
#3번 구역
for i in range(x+d1,n+1):
for j in range(1,y-d1+d2):
if new_board[i-1][j-1]==5:
break
new_board[i-1][j-1] = 3
b_3 += board[i-1][j-1]
if b_3 > b_max:
b_max = b_3
if b_3 < b_min:
b_min = b_3
# 4번 구역
# 4번 구역도 2번 구역과 마찬가지로 열이 거꾸로 해야 마지막에 5의 경계선 값을 만나게 되므로
# range를 -1 씩 거꾸로로 설정해주었다.
for i in range(x+d2+1,n+1):
for j in range(n,y-d1+d2-1,-1):
if new_board[i-1][j-1] == 5:
break
new_board[i-1][j-1] = 4
b_4 += board[i-1][j-1]
if b_4 > b_max:
b_max = b_4
if b_4 < b_min:
b_min = b_4
b_5 = total - b_1 - b_2 - b_3 -b_4
if b_5 > b_max:
b_max = b_5
if b_5 < b_min:
b_min = b_5
result = b_max - b_min
return result
min_ans = 99999999999999999999
# d1,d2,x,y 의 범위는
# 문제에서 주어진
# (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
# 를 보며 값을 지정하였다.
# x의 범위는 x+d1+d2 ≤ N 얘를 보고
# y 의 범위는 1 ≤ y-d1 와 y+d2 ≤ N 를 보고 지정했다.
for d1 in range(1,n):
for d2 in range(1,n):
for x in range(1,n-d1-d2+1):
for y in range(d1+1,n-d2+1):
ans = board_sum(x,y,d1,d2)
# 최소값 갱신
if min_ans > ans:
min_ans = ans
print(min_ans)