[파이썬] 백준 17779 : 게리맨더링2 (골드3)

[파이썬] 백준 17779 : 게리맨더링2 (골드3)

17779번: 게리맨더링 2

---

문제

---

풀이

0. 방향성 생각

• 누적합 이용해서 시간 줄이기
• 맨 위의 점을 받아서 마름모 만드는 함수 작성
• 모든 좌표가 arr 안에 들어오는지 만드는 함수 작성
• 지역 별 인구수 구하는 함수 작성

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]

cum = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not j: cum[i] = [arr[i][j]]
        else: cum[i].append(cum[i][-1]+arr[i][j])

total = 0
for i in arr : total += sum(i)

• 누적합 cum 배열 만들기
• 전체 인구 total

2. 사각형 좌표 함수, 범위 체크 함수 정의

def square(x,y,d1,d2):
    return [(x,y),(x-d1+d2,y+d1+d2),(x-d1,y+d1),(x+d2,y+d2)]

def check(points):
    for x,y in points:
        if x<0 or x>=n or y<0 or y>=n:
            return False
    return True

• 사각형 좌표 반환하는 square
• 범위 체크하는 check 함수 정의

3. 인구 구하는 함수 작성

def area(points):
    x1,y1 = points[0]
    x2,y2 = points[1]
    x3,y3 = points[2]
    x4,y4 = points[3]
    
    area1,area2,area3,area4 = 0,0,0,0
    count = 1
    for y in range(y3):
        if y < y1: area1 += cum[y][x1]
        else:
            area1 += cum[y][x1-count]
            count += 1
        if not x1-count : break

    count = 1
    for y in range(y4+1):
        if y <= y1: area2 += cum[y][-1]-cum[y][x1]
        else:
            area2 += cum[y][-1]-cum[y][x1+count]
            count += 1
        if not x1+count : break

    count = 1
    for y in range(n-1,y3-1,-1):
        if y >= y2: area3 += cum[y][x2-1]
        else:
            area3 += cum[y][x2-1-count]
            count += 1
        if not x2-count : break

    count = 0
    for y in range(n-1,y4,-1):
        if y > y2: area4 += cum[y][-1]-cum[y][x2-1]
        else:
            area4 += cum[y][-1]-cum[y][x2+count]
            count += 1
        if not x2+count : break

    population = [area1,area2,area3,area4]
    population.append(total - sum(population))
    return max(population)-min(population)

• 상하좌우 순으로 square의 좌표가 들어온다.
• 그림 보면서 누적합 이용해서 채워주기.
• 인덱스 에러 나지않게 break문 사용 (사각형 끝 점이 경계에 있으면 다음 루프에서 탈출해서 에러발생 할 수 있다)

4. 출력

answer = []
for x in range(n):
    for y in range(n):
        for d1 in range(1,n):
            for d2 in range(1,n):
                point = square(x,y,d1,d2)
                if check(point):
                    answer.append(area(point))

print(min(answer))

• 여기서도 d1+d2 넘어가면 n 넘어가면 커트시켜서 단축시킬 수 있다. 귀찮아서 패스

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]

cum = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not j: cum[i] = [arr[i][j]]
        else: cum[i].append(cum[i][-1]+arr[i][j])

total = 0
for i in arr : total += sum(i)

def square(x,y,d1,d2):
    return [(x,y),(x-d1+d2,y+d1+d2),(x-d1,y+d1),(x+d2,y+d2)]

def check(points):
    for x,y in points:
        if x<0 or x>=n or y<0 or y>=n:
            return False
    return True


def area(points):
    x1,y1 = points[0]
    x2,y2 = points[1]
    x3,y3 = points[2]
    x4,y4 = points[3]
    
    area1,area2,area3,area4 = 0,0,0,0
    count = 1
    for y in range(y3):
        if y < y1: area1 += cum[y][x1]
        else:
            area1 += cum[y][x1-count]
            count += 1
        if not x1-count : break

    count = 1
    for y in range(y4+1):
        if y <= y1: area2 += cum[y][-1]-cum[y][x1]
        else:
            area2 += cum[y][-1]-cum[y][x1+count]
            count += 1
        if not x1+count : break

    count = 1
    for y in range(n-1,y3-1,-1):
        if y >= y2: area3 += cum[y][x2-1]
        else:
            area3 += cum[y][x2-1-count]
            count += 1
        if not x2-count : break

    count = 0
    for y in range(n-1,y4,-1):
        if y > y2: area4 += cum[y][-1]-cum[y][x2-1]
        else:
            area4 += cum[y][-1]-cum[y][x2+count]
            count += 1
        if not x2+count : break

    population = [area1,area2,area3,area4]
    population.append(total - sum(population))
    return max(population)-min(population)


answer = []
for x in range(n):
    for y in range(n):
        for d1 in range(1,n):
            for d2 in range(1,n):
                point = square(x,y,d1,d2)
                if check(point):
                    answer.append(area(point))

print(min(answer))

 

코멘트

인덱스 실수 줄이고 빠르게 풀어야한다 ....