[Python]백트래킹 백준 14889

   문제

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

역시나 기본에 충실한 문제인거같다.

두팀으로 나누는 경우에 수를 모두 구해 각 경우마다 팀의 능력치를 구해서 가장 작은 차

를 출력하면 된다.처음 작성한 코드는 조금 느려서 처음엔 시간초과가 떴다.

import sys
 
 
n=int(sys.stdin.readline())
 
startlink=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
team=[0 for _ in range(n)]    #0은
 
 
result=9999999999999
#팀을 나누는 경우의수
#팀을 나누고 난뒤 각각의 차 구해서 최소값찾기
def maketeam(index,j):
    if index==n//2:
        global result
        start = 0#스타트팀합
        link = 0#링크팀합
        for i in range(n):
            for j in range(n):
                if team[i]==0 and team[j]==0:
                    start+=startlink[i][j]
                elif team[i]==1 and team[j]==1:
                    link+=startlink[i][j]
        if start>link:
            if result>start-link:
                result=start-link
        else:
            if result>link-start:
                result=link-start
        return
        #모두 더해서 두수의 차비교
    else:
        for i in range(j,n):
            if team[i]==0:#팀정하기
                team[i]=1
                maketeam(index+1,i)
                team[i]=0
            else:
                continue
 
maketeam(0,0)
print(result)

중복이 굉장히 많고 배열처리과정에서 계속 비교하는것도 오래 걸리는 원인인거 같다.

3개를 뽑는데 뽑은것에 순서가 없다.

1번 사람이 있는팀과 없는팀으로도 나눌수 있을것이다.

배열은 매번 비교하는게 아니라 각각의 배열에 넣어서 한번에 비교하게 하였다.

import sys
 
n=int(sys.stdin.readline())
 
startlink=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
team=[0 for _ in range(n)]
 
count=0
result=9999999999999
#팀을 나누는 경우의수
#팀을 나누고 난뒤 각각의 차 구해서 최소값찾기
def maketeam(index,j):
    if index==n//2:
        global result
        global count
        start = 0#스타트팀합
        link = 0
        count+=1
        start_list=[] #담아서 비교
        link_list=[]
        for i in range(n):
            if team[i]==1:
                start_list.append(i)
            else:
                link_list.append(i)
 
 
        for i in range(len(start_list)):
            for j in range(len(start_list)):
                    start+=startlink[start_list[i]][start_list[j]]
                    link+=startlink[link_list[i]][link_list[j]]
        if start>link:
            if result>start-link:
                result=start-link
        else:
            if result>link-start:
                result=link-start
        return
        #모두 더해서 두수의 차비교
    else:
        for i in range(j,n):
            if team[i]==0:#팀정하기
                team[i]=1
                maketeam(index+1,i)
                team[i]=0
            else:
                continue
 
team[0]=1#1을 팀에 넣고 시작한다 반으로 줄어든다.
maketeam(1,0)
print(result)

완벽하지는 않지만 최적화를 통해 통과할수 있을정도로 만들었다.