17779번 - 게리멘더링2

문제

 

17779번: 게리맨더링 2 (acmicpc.net)

17779번: 게리맨더링 2

풀이 1

두 코드를 잘 비교해보자.

N = int(input())
A = [[0]*(N+1)]
sum_total = 0
for _ in range(N):
    li = []
    for elem in map(int, input().split()):
        li.append(elem)
        sum_total += elem
    A.append([0] + li)


def get_result(x,y,d1,d2):
    p_list = [0]*6
    col1 = y
    for _row in range(1,x+d1):
        if _row >= x:
            col1 -= 1
        p_list[1] += sum(A[_row][:col1+1])
    col2 = y+1
    for _row in range(1,x+d2+1):
        if _row > x:
            col2 += 1
        p_list[2] += sum(A[_row][col2:])
    col3 = y-d1+d2-1
    for _row in range(N,x+d1-1,-1):
        if _row < x+d1+d2:
            col3 -= 1
        p_list[3] += sum(A[_row][:col3+1])
    col4 = y-d1+d2
    for _row in range(N,x+d2,-1):
        if _row <= x+d1+d2:
            col4 += 1
        p_list[4] += sum(A[_row][col4:])
    p_list[5] = sum_total - sum(p_list)
    p_list.sort()
    return p_list[5]-p_list[1]


def split_sector(x,y,d1,d2):
    global answer
    if x + d1 + d2 <= N and y + d2 <= N and y - d1 >= 1 :
        answer = min(answer, get_result(x,y,d1,d2))
        split_sector(x,y,d1+1,d2)
        split_sector(x,y,d1,d2+1)


answer = int(1e9)
for row in range(1,N-1):
    for col in range(2,N):
        split_sector(row,col,1,1)

print(answer)

위 코드는 재귀 함수를 통해서 d1,d2를 구하고 있고, 아래는 이중 for문을 통해서 구하고 있다.

N = int(input())
A = [[0]*(N+1)]
sum_total = 0
for _ in range(N):
    li = []
    for elem in map(int, input().split()):
        li.append(elem)
        sum_total += elem
    A.append([0] + li)


def get_result(x,y,d1,d2):
    p_list = [0]*6
    col1 = y
    for _row in range(1,x+d1):
        if _row >= x:
            col1 -= 1
        p_list[1] += sum(A[_row][:col1+1])
    col2 = y+1
    for _row in range(1,x+d2+1):
        if _row > x:
            col2 += 1
        p_list[2] += sum(A[_row][col2:])
    col3 = y-d1+d2-1
    for _row in range(N,x+d1-1,-1):
        if _row < x+d1+d2:
            col3 -= 1
        p_list[3] += sum(A[_row][:col3+1])
    col4 = y-d1+d2
    for _row in range(N,x+d2,-1):
        if _row <= x+d1+d2:
            col4 += 1
        p_list[4] += sum(A[_row][col4:])
    p_list[5] = sum_total - sum(p_list)
    p_list.sort()
    return p_list[5]-p_list[1]


answer = int(1e9)
for row in range(1,N-1):
    for col in range(2,N):
        for a in range(1,N+1):
            for b in range(1,N+1):
                if row+a+b <= N and col+b <= N and col-a >= 1:
                    answer = min(answer,get_result(row,col,a,b))
print(answer)

결국 이중 for 문을 쓰는편이 훨씬 빨랐는데, 경험적으로 이런 상황엔 재귀함수를 피하도록 하자.

풀이 2

재귀함수로 구현하면 중복된 중복순열(?!) 이 나온다. 직관적으로 이중 for문을 이용해서 중복순열을 구현하는것이 훨씬 편하고 빠르다.

추가로 generator를 이용해서 순열,조합,중복순열,중복조합을 만드는 법을 찾아봤는데, 나중에 유용하게 써먹을 수 있을것 같아서 남겨본다.

def combinations(li,r):
    for i in range(len(li)):
        if r == 1:
            yield [li[i]]
        else:
            for next in combinations(li[i+1:],r-1):
                yield [li[i]] + next


def permutations(li,r):
    for i in range(len(li)):
        if r == 1:
            yield [li[i]]
        else:
            for next in combinations(li[:i]+li[i+1:],r-1):
                yield [li[i]] + next


def product(li,r):
    for i in range(len(li)):
        if r == 1:
            yield [li[i]]
        else:
            for next in product(li,r-1):
                yield [li[i]] + next


def combinations_with_replacement(li,r):
    for i in range(len(li)):
        if r == 1:
            yield [li[i]]
        else:
            for next in combinations_with_replacement(li[i:],r-1):
                yield [li[i]] + next

아무튼 구조 자체는 매우 간단하지만, 각 선거구를 나누는게 조금 까다롭게 느껴질 수 있는데 이는 이차원 평면 좌표계로 접근하면 슬라이싱보다 훨씬 직관적으로 풀이할 수 있다.

N = int(input())
A = [[0]*(N+1)]
for _ in range(N):
    A.append([0] + list(map(int,input().split())))


def get_answer(x,y,d1,d2):
    global answer
    visited = [[0]*(N+1) for _ in range(N+1)]
    population = [0]*5
    # 5번 선거구 먼저
    for row in range(1,N+1):
        for col in range(1,N+1):
            if x+y <= row+col <= x+y+2*d2 and x-y <= row-col <= x-y+2*d1:
                visited[row][col] = 5
                population[4] += A[row][col]
    # 나머지 선거구
    for row in range(1,N+1):
        for col in range(1,N+1):
            if visited[row][col] == 0:

                # 1번 선거구
                if 1 <= row < x+d1 and 1 <= col <= y:
                    visited[row][col] = 1
                    population[0] += A[row][col]
                # 2번 선거구
                elif 1 <= row <= x+d2 and y < col <= N:
                    visited[row][col] = 2
                    population[1] += A[row][col]
                # 3번 선거구
                elif x+d1 <= row <= N and 1 <= col < y-d1+d2:
                    visited[row][col] = 3
                    population[2] += A[row][col]
                # 4번 선거구
                else:
                    visited[row][col] = 4
                    population[3] += A[row][col]
    # 인구수 최대, 최소 차
    population.sort()
    result = population[-1] - population[0]
    answer = min(answer,result)


answer = int(1e9)
d_li = list(range(1,N+1))
for row in range(1,N-1):
    for col in range(2,N):
        for d1 in range(1,N+1):
            if not (row+d1+1 <= N and col-d1 >= 1):
                break
            for d2 in range(1,N+1):
                if row+d1+d2 <= N and col+d2 <= N:
                    get_answer(row,col,d1,d2)
                else:
                    break
print(answer)