[Python/파이썬] - 백준(BOJ) 25046번 : 사각형 게임 (small)

https://www.acmicpc.net/problem/25046

25046번: 사각형 게임 (Small)

 

브루트포스 방식으로 민우가 고를 수 있는 경우의 수를 모두 실행한다

n이 5일때는 아무것도 고르지 않는 것부터 0,1,2,3,4 모두 고르는 것 까지 모두 탐색한다

이후 종진이는 자신이 가장 이득을 볼 수 있는 경우를 고르기 때문에 

col 배열을 만들어 이미 민우가 골랐다면 +, 고르지 않았다면 -를 하여 더해준다

반복한 후 sort하여 0 이상인 최대값들을 민우가 획득한 점수에서 빼준다.

민우가 획득한 점수의 최대값을 갱신한다.

 

import sys
input = sys.stdin.readline

answer = -sys.maxsize
def choice(que, ind, val, lim):
    global answer
    if val == lim:
        s = 0
        row = [0] * n
        col = [0] * n
        for y in que:
            s += sum(arr[y])
        for i in range(n):
            for j in range(n):
                if i in que:
                    col[j] += arr[i][j]
                else:
                    col[j] -= arr[i][j]
        col.sort(reverse=True)
        for i in range(n):
            if col[i] <= 0:
                break
            s -= col[i]
        answer = max(answer, s)
        choice(que, ind, val, lim+1)
        return

    for i in range(ind+1, n):
        que.append(i)
        choice(que, i, val+1, lim)
        que.pop()

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
choice([], -1, 0, 0)
print(answer)