백준 14889 스타트와 링크

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

조합을 구하는 문제.

조합을 구하고 단순히 그래프 순회를 통해 합을 구해주는 문제였다.

from itertools import combinations
import math
n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

combi = list(combinations(range(n), n//2))

answer = math.inf

def getstat(members):
    num = 0
    for member in members:
        for i in range(n):
            if i in members:
                num += graph[member][i]
    return num

for comb in combi:
    ateam = getstat(comb)
    b = [i for i in range(n) if i not in comb]
    bteam = getstat(b)

    answer = min(answer,abs(ateam - bteam))

print(answer)

좋은 웹페이지 즐겨찾기