[backjoon] 14889 스타트와 링크 (python)

문제 14889번: 스타트와 링크

BruteForce 문제

이 문제는 축구를 하기 위해 모인 사람 짝수인 N을 입력받아서 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야한다. 그 후 스타트 팀과 링크 팀의 능력치를 구해서 두 팀 차이의 최솟값을 출력하는 문제이다.
팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다.
오잉... 이게 무슨 소리인고... 예시로 알아보쟈!

1, 4번이 스타트팀, 2, 3번이 링크 팀에 속한 경우, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S14 + S41 = 3 + 3 = 6
• 링크 팀: S23 + S32 = 5 + 1 = 6

예제 입력

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력

0

---

문제풀이

파이썬에서는 itertools 모듈이 있어서 조합을 구하기가 쉽다.
n명의 인원 중에서 n/2의 인원을 뽑고 나머지 인원은 set으로 차집합시켜서 빼주고
스타트 팀과 링크 팀의 능력치를 각각 구해주고 min()과 abs()를 이용하여 최소가 되는 차를 구하면 된다.

---

N = 4
member = [0, 1, 2, 3]
power_list = [[0, 1, 2, 3], [4, 0, 5, 6], [7, 1, 0, 2], [3, 4, 5, 0]]
일때 조합으로 가능한 팀을 생성해준다.
from itertools import combinations 조합함수를 이용한다.

#조합으로 가능한 팀 생성해주기
for team in list(combinations(member, N//2)):
    possible_team.append(team)

# print(possible_team)
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

• 스타트 팀: 1, 2번 | 1, 3번 | 1, 4번 | 2, 3번 | 2, 4번 | 3, 4번
• 링크 팀 : 3, 4번 | 2, 4번 | 2, 3번 | 1, 4번 | 1, 3번 | 1, 2번
  으로 경우의 수를 구해야한다.

ex ) 1, 2번이 스타트 팀, 3, 4번이 링크 팀

• 스타트 팀 : (0, 1) S01 + S10 = 1 + 4 = 5
• 링크 팀 : (2, 3) S23 + S32 = 2 + 5 = 7

for t1 in combinations(member, N//2):
    # start, link 능력치
    start, link = 0, 0
    t2 = list(set(member) - set(t1))
    # t1 = (0, 1)
    # t2 = [2, 3]
    for t in combinations(t1, 2):
        # t = (0, 1)
        start += power_list[t[0]][t[1]]
        start += power_list[t[1]][t[0]]
        # start = 1 + 4 = 5
    for t in combinations(t2, 2):
        # t = [2, 3] 
        link += power_list[t[0]][t[1]]
        link += power_list[t[1]][t[0]]
        # link = 2 + 5 = 7

스타트 팀과 링크 팀의 능력치를 각각 구해주고 min()과 abs()를 이용하여 최소가 되는 차를 구하면 된다.

result = min(result, abs(start - link))

---

전체코드

import sys
from itertools import combinations #조합 함수
input = sys.stdin.readline

N = int(input())
member = [i for i in range(N)]
power_list = []

#팀 생성해주기
for _ in range(N):
    power_list.append((list(map(int, input().split()))))

result = int(1e9)
for t1 in combinations(member, N//2):
    # start, link 능력치
    start, link = 0, 0
    t2 = list(set(member) - set(t1))
    # 스타트 팀
    for t in combinations(t1, 2):
        start += power_list[t[0]][t[1]]
        start += power_list[t[1]][t[0]]
    # 링크 팀
    for t in combinations(t2, 2):
        link += power_list[t[0]][t[1]]
        link += power_list[t[1]][t[0]]
    result = min(result, abs(start - link))
print(result)

---

너모 어렵다...🤯🤯🤯
출처 #321 백준 파이썬 [14889] 스타트와 링크
출처 [BOJ][Python] 백준 14889번 - 스타트와 링크