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

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

# 백준 14889 스타트와 링크
from collections import deque
N=int(input())
field=[]
for _ in range(N):
    field.append(list(map(int,input().split()))) #전체 경우 저장

visited=[0 for _ in range(N)]
team=deque()
ans=10**9 
def team_match(curr): #팀에 인원을 추가하여, 팀을 두개로 분리하여(방문한 팀 vs 방문안한 팀) 차이 비교
    global ans
    if len(team)==N//2:
        team_ano=deque()
        for i in range(N):
            if visited[i]==0:
                team_ano.append(i)
        A_team_score=0
        B_team_score=0
        for i in range(len(team)):
            for j in range(i+1,len(team)):
                A_team_score+=(field[team[i]][team[j]]+field[team[j]][team[i]])
                B_team_score+=(field[team_ano[i]][team_ano[j]]+field[team_ano[j]][team_ano[i]])
        diff=abs(B_team_score-A_team_score)
        if diff<ans:
            ans=diff
        if diff==0:
            print(0)
            exit()
    for i in range(curr,N):
        if visited[i]==0:
            visited[i]=1
            team.append(i)
            team_match(i)
            team.pop()
            visited[i]=0

for k in range(N): 
    team_match(k)

print(ans)

코드를 구현하였는데 겨우 턱걸이로 통과하였다.

 

생각해보니 굳이 for k in range(N)을 통해 모든 경우를 확인할 필요가 없었다.

# 백준 14889 스타트와 링크
from collections import deque
N=int(input())
field=[]
for _ in range(N):
    field.append(list(map(int,input().split()))) #전체 경우 저장

team=deque()
ans=10**9 
def team_match(curr): #팀에 인원을 추가하여, 팀을 두개로 분리하여(방문한 팀 vs 방문안한 팀) 차이 비교
    global ans
    if len(team)==N//2:
        team_ano=[i for i in range(N) if i not in team]
        A_team_score=0
        B_team_score=0
        for i in range(len(team)):
            for j in range(i+1,len(team)):
                A_team_score+=(field[team[i]][team[j]]+field[team[j]][team[i]])
                B_team_score+=(field[team_ano[i]][team_ano[j]]+field[team_ano[j]][team_ano[i]])
        diff=abs(B_team_score-A_team_score)
        if diff<ans:
            ans=diff
        if diff==0:
            print(0)
            exit()
    for i in range(curr,N):
        if i not in team:
            team.append(i)
            team_match(i)
            team.pop()

team_match(0)

print(ans)

반복문을 삭제하니 시간이 절반으로 줄었다.

 

 

<GPT 코드>

import sys
from itertools import combinations

def calculate_score(team, S):
    score = 0
    for i in range(len(team)):
        for j in range(i + 1, len(team)):
            score += S[team[i]][team[j]] + S[team[j]][team[i]]
    return score

def solve():
    n = int(sys.stdin.readline().strip())
    S = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
    players = list(range(n))
    min_diff = float('inf')

    for team1 in combinations(players, n // 2):
        team2 = tuple(set(players) - set(team1))  # 나머지 팀 자동 결정
        score1 = calculate_score(team1, S)
        score2 = calculate_score(team2, S)
        min_diff = min(min_diff, abs(score1 - score2))
        
        if min_diff == 0:  # 조기 종료
            break

    print(min_diff)

solve()

GPT의 최적화 코드를 첨부한다.