[ 백준 ] 14889번 : 스타트와 링크 (파이썬)

문제 )

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

14889번: 스타트와 링크

 

[ 풀이 ]

이 문제는 브루트 포스 (Brute Force) Algorithm을 이용해서 풀어주었다.

1~N번까지의 사람들을 2개의 팀으로 나눠야하는데 itertools library의 combinations 함수를 이용하여 

N개를 2개의 group으로 만들어주는 순열을 구해 문제를 푼다. 

 

우선, 두팀의 능력치의 차를 구해주는 함수인 teamsub function을 만들어 주었다.

✔ startteam의 능력치 → stsum (initialize 0)
✔ linkteam의 능력치 → lksum (initialize 0)

stratteam과 linkteam의 능력치를 각각 구해서 빼주는 기능을 한다. 

 

 

< Solvemin Function의 Algorithm >

✔ 최솟값 변수 → mini ( 처음 큰값으로 초기화)

1. N명의 멤버중 N/2명을 고르는 순열 전부 → startteam
2. startteam에 접근하는 변수 → st ( st는 1개의 순열 list 의미 )
              전체 멤버에서 st팀에 속한 멤버 빼주기  → linkteam  ( st의 멤버 제외한 다른팀 멤버 list )
              startteam과 linkteam의 능력치 차이 구해주기  → teamsub Function 이용
              이전 팀간의 과 신규 팀간의 능력치 차이 비교하고 최솟값 갱신

 

 

- python code 

from itertools import combinations
import sys
input= sys.stdin.readline

def teamsub(st,lt):
    stsum,lksum=0,0
    #startteam 능력치 구하기
    for i in st:
        for j in st:
            stsum+=S[i][j]
    # Linkteam 능력치 구하기 
    for i in lt:
        for j in lt:
            lksum+=S[i][j]
    return abs(stsum-lksum)


def Solvemin():
    mini=100000
    # Team 만들어주고 최솟값 정하기 
    startteam=list(combinations(allmember,N//2)) # N명의 멤버중 N/2명을 고르는 all 순열 
    for st in startteam:
        linkteam=list(set(allmember)-set(st)) 
        mini=min(mini,teamsub(st,linkteam)) # min값 update가능하면 update
    print(mini)
    

N=int(input())
allmember=[i for i in range(N)]
S=[]

for i in range(N):
    mid=list(map(int,input().split()))
    S.append(mid)
Solvemin()