[백준] 14889 스타트와 링크 파이썬 python

문제링크

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

14889번: 스타트와 링크

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
w = [list(map(int,input().split())) for _ in range(n)]
 
#1) 팀을 나누어야함 combination 최대 : calTeam
#2) 팀에서 2명씩 골라서 pairs를 만듦 : calPairs
#3) pairs끼리 합 더해서 팀의 최종 sum 구하기 : calSum
 
teams = []
 
def calTeam(start, team):
    if len(team)==n/2:
        tmp = list(team)
        teams.append(tmp)
        return 
    for i in range(start, n):
        if i not in team:
            team.append(i)
            calTeam(i+1, team)
            team.pop()
 
def calPairs(start, team, tmp):
    if len(tmp)==2:
        temp = list(tmp)
        pairs.append(temp)
        return
    for i in range(start, len(team)):
        if team[i] not in tmp:
            tmp.append(team[i])
            calPairs(i+1, team, tmp)
            tmp.pop()
    
def calSum(pairs):
    sum = 0
    for pair in pairs: #pair = (0,1) index가 들어가있음
        i,j = pair
        sum += w[i][j]+w[j][i]
    return sum
   
calTeam(1, [0]) 
ans = float('inf')
 
for i in teams:
    teamA = i
    teamB = [j for j in range(n) if j not in teamA]
    pairs = []
    calPairs(0, teamA, [])
    pairsA = list(pairs)
    pairs = []
    calPairs(0, teamB,[])
    pairsB = list(pairs)
 
    sumA = calSum(pairsA)
    sumB = calSum(pairsB)
    tmp = abs(sumA-sumB)
    if tmp<ans:
        ans = tmp
print(ans)
 
 
 

 

POINT

- 풀이방법:

내가 접근한 방법은 

1)TeamA, TeamB로 2등분한 뒤 ,              -----> calTeam()

2)Team 내에서 2명씩 묶은 다음에(pair)  -----> calPairs()

3) 팀 별 능력치를 계산하는 것이다.            -----> calSum()

이를 구현하기 위해 combination을 2번 사용하였다.

 

1) calTeam(start, team) : n명을 2등분 하는 함수 

start : 새로 포함시기기 시작할 index

team : 현재까지 추가한 index       *(len(team) == n//2 면 끝, 2등분 다 함)

계산 복잡도  :  n명에서 n//2 만큼 선택하는 것인데, 여기서 추가로 더 줄일 수 있다.

왜냐하면, 총 6명이라 할 때, TeamA = {0,1,2} TeamB = {3,4,5} 인 상황과  반대로 TeamA ={3,4,5} TeamB =  {0,1,2} 인 상황은 같기 때문에 TeamA에 미리 0번 idex를 고정으로 포함시켜도 된다. 따라서 calTeam(0,[]) 가 아닌 calTeam(1,[0]) 로 시작하였다. 

 

 

2) calPairs (start, team, tmp): Team 내의 n//2 명에서 2명씩 고르는 함수

start : 새로 포함시기기 시작할 index

tean : 추가할 전체 index 후보군

tmp : team에서 현재까지 추가한 index     *(len(tmp) ==2 면 끝, 2명 다 고름)