파이썬 알고리즘 131번 | [백준 14889번] 스타트와 링크-예외 찾아내기

131. 스타트와 링크

1) 어떤 전략(알고리즘)으로 해결?

(1) 우선 팀을 반으로 가르는 모든 경우 구해뜸

import sys
def findteam(arr,N,M):#일단 팀을 반으로 가르는 모든 경우를 구해
    if N==n//2:
        ex2=[]*(n//2)
        for i in range(1,n+1):
            if i not in ex1:
                ex2.append(i)
        print(ex1)
        print(ex2)

    else :
        for i in range(M,n):
            if chk[i]==0:
                chk[i]=1
                ex1.append(i)
                findteam(arr,N+1,i+1)
                ex1.pop()
                chk[i]=0

# def findmini(ex1,ex2):#조합방식으로 ex1 합 구하고 /ex2 합 구하고 / 두개 합 빼서 return해

if __name__=="__main__":
    n=int(input())

    mini=1000000
    ex1=[]*(n//2)

    chk=[0]*(n+1)#1부터 n까지

    arr=[0]*(n)

    for i in range(n):
        arr[i]=list(map(int,sys.stdin.readline().split()))
    findteam(arr,0,1)
    #arr은 배열

=> ex1,ex2라는 배열이 각각 팀1,2의 경우

(2) 이 반으로 가르는 모든 경우에 해당하는 표값 조합을 구하는 findmini 구현하기

def findmini(ex,num,mum,res)->int:#조합방식으로 ex1 2개씩 조합하는 것 계산해서 return
    if len(ex)==2:
        return arr[ex[0]-1][ex[1]-1]+arr[ex[1]-1][ex[0]-1]
    elif num==2:
        tot.append(arr[res[0]-1][res[1]-1]+arr[res[1]-1][res[0]-1])

    else :
        for i in range(mum,n//2):
            if chk2[i]==0:
                chk2[i]=1
                res.append(ex[i])
                findmini(ex,num+1,i+1,res)
                res.pop()
                chk2[i]=0

---

2) 코딩 설명

<내 풀이>

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

import sys
def findteam(arr,N,M):#일단 팀을 반으로 가르는 모든 경우를 구해
    global mini
    global tot
    tot=[]
    if N==n//2:
        ex2=[]*(n//2)
        for i in range(1,n+1):
            if i not in ex1:
                ex2.append(i)
        res1=[]
        res2=[]

        findmini(ex1,0,0,res1)
        # print("resa tot\n",ex1)
        # print(tot)
        tot1=sum(tot)
        tot=[]

        findmini(ex2,0,0,res2)
        # print("resb tot\n",ex2)
        # print(tot)
        tot2=sum(tot)

        ab=abs(tot1-tot2)
        if mini>ab:
            mini=ab

    else :
        for i in range(M,n):
            if chk[i]==0:
                chk[i]=1
                ex1.append(i)
                findteam(arr,N+1,i+1)
                ex1.pop()
                chk[i]=0

def findmini(ex,num,mum,res)->int:#조합방식으로 ex1 2개씩 조합하는 것 계산해서 return
    if len(ex)==2:
        return arr[ex[0]-1][ex[1]-1]+arr[ex[1]-1][ex[0]-1]
    elif num==2:
        tot.append(arr[res[0]-1][res[1]-1]+arr[res[1]-1][res[0]-1])

    else :
        for i in range(mum,n//2):
            if chk2[i]==0:
                chk2[i]=1
                res.append(ex[i])
                findmini(ex,num+1,i+1,res)
                res.pop()
                chk2[i]=0

if __name__=="__main__":

    n=int(input())
    mini=1000000
    ex1=[]*(n//2)
    chk=[0]*(n+1)#1부터 n까지
    chk2=[0]*(n//2+1)
    arr=[0]*(n)
    for i in range(n):
        arr[i]=list(map(int,sys.stdin.readline().split()))
    findteam(arr,0,1)
    print(mini)
    #arr은 배열

-> 90% 넘겨서 갑자기 틀림

• 어떤 부분일까잉
• 어떤 예외처리를 안할걸까??
• 20까지

---

다른 분의 풀이

from itertools import combinations #조합 함수

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
members = [i for i in range(N)]
possible_team = []

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

min_stat_gap = 10000 #갭이 가장 작은 값을 찾기 위하여
for i in range(len(possible_team)//2):
    #A 팀
    team = possible_team[i]
    stat_A = 0 #A팀 능력치
    for j in range(N//2):
        member = team[j] #멤버
        for k in team:
            stat_A += S[member][k] #멤버와 함께할 경우의 능력치들
            
    #A를 제외한 나머지 팀
    team = possible_team[-i-1]
    stat_B = 0
    for j in range(N//2):
        member = team[j]
        for k in team:
            stat_B += S[member][k]
            
    min_stat_gap = min(min_stat_gap, abs(stat_A - stat_B))
    
print(min_stat_gap)

<반성 점>

<배운 점>

• 파이썬에 순열, 조합을 제공해주는 라이브러리가 존재한다