문제 링크
문제 설명
N*N 크기의 재현시의 선거구를 공평하게 확정하려고 한다. (r,c)는 재현시의 r행 c열 구역을 의미하고, 이는 5개의 선거구중 하나에 포함된다. 선거구 포함 구현은 모두 연결되어야 한다. 이때 연결이란, 구역 A에서 같은 선거구에 포함되는 인접 구역을 0개 이상 통해 B로 갈 수 있을때를 의미한다.
선거구는 다음과 같이 나뉜다.
- 기준점 (x, y)와 경계의 길이 d1, d2 정하기
- 다음 칸은 경계선이다.
(x, y), (x+1, y-1), ..., (x+d1, y-d1)
(x, y), (x+1, y+1), ..., (x+d2, y+d2)
(x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
-> 경계선과 경계선 안에 포함되는 구역은 5번 구역이다. - 5번 선거구에 포함되지 않은 나머지 구역은 다음과 같이 정해진다.
1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
선거구의 인기는 선거구에 포함되는 구역의 모든 인구를 말한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 차이 최소값은?
문제 풀이
for x in range(N):
for y in range(N):
# 가능한 모든 d1, d2 찾기
for d1 in range(1, y+1):
for d2 in range(1, N-y):
if d1+d2 <= N-x-1:
answer = min(answer, seperate(x, y, d1, d2))
print(answer)가능한 모든 x, y, d1, d2 경우에 대해서 구역을 나눈다.
seperate 함수는 다음과 같이 구현했다.
def seperate(x, y, d1, d2):
seperated = [[0 for _ in range(N)] for _ in range(N)]
population = [0 for _ in range(5)]
# 5번 선거구
for i in range(d1+1):
seperated[x+i][y-i] = 5
seperated[x+d2+i][y+d2-i] = 5
for i in range(d2+1):
seperated[x+i][y+i] = 5
seperated[x+d1+i][y-d1+i] = 5
for i in range(N):
for j in range(N):
if seperated[i][j] == 5:
k = j+1
while k<N and seperated[i][k] != 5:
k+= 1
if k<N:
# j~k까지 5로
for l in range(j+1, k):
seperated[i][l] = 5
break
# 1번 선거구
for i in range(x+d1):
for j in range(y+1):
if seperated[i][j] != 5:
seperated[i][j] = 1
# 2번 선거구
for i in range(x+d2+1):
for j in range(y+1, N):
if seperated[i][j] != 5:
seperated[i][j] = 2
# 3번 선거구
for i in range(x+d1, N):
for j in range(y-d1+d2):
if seperated[i][j] != 5:
seperated[i][j] = 3
# 4번 선거구
for i in range(x+d2+1, N):
for j in range(y-d1+d2, N):
if seperated[i][j] != 5:
seperated[i][j] = 4
for i in range(N):
for j in range(N):
population[seperated[i][j]-1] += board[i][j]
return max(population) - min(population)문제의 인덱스는 1부터, 나는 0부터 시작해서 꽤 헤맸다 ^_ㅠ
전체 코드
import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
answer = float('inf')
def seperate(x, y, d1, d2):
seperated = [[0 for _ in range(N)] for _ in range(N)]
population = [0 for _ in range(5)]
# 5번 선거구
for i in range(d1+1):
seperated[x+i][y-i] = 5
seperated[x+d2+i][y+d2-i] = 5
for i in range(d2+1):
seperated[x+i][y+i] = 5
seperated[x+d1+i][y-d1+i] = 5
for i in range(N):
for j in range(N):
if seperated[i][j] == 5:
k = j+1
while k<N and seperated[i][k] != 5:
k+= 1
if k<N:
# j~k까지 5로
for l in range(j+1, k):
seperated[i][l] = 5
break
# 1번 선거구
for i in range(x+d1):
for j in range(y+1):
if seperated[i][j] != 5:
seperated[i][j] = 1
# 2번 선거구
for i in range(x+d2+1):
for j in range(y+1, N):
if seperated[i][j] != 5:
seperated[i][j] = 2
# 3번 선거구
for i in range(x+d1, N):
for j in range(y-d1+d2):
if seperated[i][j] != 5:
seperated[i][j] = 3
# 4번 선거구
for i in range(x+d2+1, N):
for j in range(y-d1+d2, N):
if seperated[i][j] != 5:
seperated[i][j] = 4
for i in range(N):
for j in range(N):
population[seperated[i][j]-1] += board[i][j]
return max(population) - min(population)
for x in range(N):
for y in range(N):
# 가능한 모든 d1, d2 찾기
for d1 in range(1, y+1):
for d2 in range(1, N-y):
if d1+d2 <= N-x-1:
answer = min(answer, seperate(x, y, d1, d2))
print(answer)
소요 시간
1시간 반!
Hongik CE