백준 / 스타트와 링크 / 14889번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 스타트와 링크 / 14889번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/14889

 

문제 설명

---

나의 풀이

from itertools import combinations


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

    min_diff = int(1e9)

    # 가능한 팀 조합 절반만 순회
    people = list(range(n))
    for team1 in combinations(people, n // 2):
        team2 = list(set(people) - set(team1))

        # 팀 능력치 계산
        def team_score(team):
            score = 0
            for i in team:
                for j in team:
                    if i != j:
                        score += arr[i][j]
            return score

        diff = abs(team_score(team1) - team_score(team2))
        min_diff = min(min_diff, diff)

        if min_diff == 0:
            break  # 최적값 조기 종료

    print(min_diff)


if __name__=="__main__":
    solution()

---

※ 알아야 할 것

예를 들어서 [0, 1]이 team 1일 때 team2 팀에는 [0, 1]이 들어가면 안됩니다!

[0,1]	[2,3]	서로 겹치지 않음
[0,2]	[1,3]	서로 겹치지 않음
[0,3]	[1,2]	서로 겹치지 않음
[0,1]	[0,2]	0번이 겹침
[1,2]	[2,3]	2번이 겹침

from itertools import combinations
print(list(combinations([0,1,2,3], 2)))

# 결과 [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]