[Codetree] 수들의 합 최대화하기 Python

https://www.codetree.ai/missions/2/problems/max-sum-of-numbers/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

n = int(input())

graph = []
for _ in range(n):
    temp = list(map(int, input().rstrip().split(" ")))
    graph.append(temp)

visited = [0 for _ in range(n)]

row = [i for i in range(n)]
num = [i for i in range(n)]


cnt = 0
result = []
answer = []


def find_max(col):
    cnt = 0
    for i, j in zip(row, col):
        cnt += graph[i][j]
    return cnt

def backtrack(dep):
    global cnt

    if dep == n:
        temp = answer[::]
        result.append(temp)
        cnt = max(find_max(temp), cnt)
        return

    
    for i in range(n):
        if not visited[i]:
            answer.append(num[i])
            visited[i] = 1
            backtrack(dep+1)
            answer.pop()
            visited[i] = 0


backtrack(0)

print(cnt)