https://www.acmicpc.net/problem/14889
14889번: 스타트와 링크예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.www.acmicpc.net
맨처음에 itertools로풀었다.
굳이 모든 콤비에 대하여 다 구할 필요 없이,
콤비의 반만 계산하면 나머지는 스타트와 링크가 바뀐 경우이므로,
반만 계산한다.
from itertools import combinationsimport sysinput=sys.stdin.readline
n=int(input())arr=[]for _ in range(n):
arr.append([*map(int,input().split())])all_people=[x for x in range(n)]
start_teams=list(combinations(all_people,n//2))
start_teams=start_teams[:len(start_teams)//2]all_people=set(all_people)
answer=1e+10for start in start_teams: link=list(set(start)^all_people)
start_score=0 link_score=0 for i in range(n//2):
for j in range(n//2): start_score+=arr[start[i]][start[j]]
link_score+=arr[link[i]][link[j]] tmp=abs(start_score-link_score)
if tmp<answer: answer=tmpprint(answer)문제는 dfs로 풀 때 정답코드를 변수명만 다르게해서 배껴도 문제가 생긴다는 점이다.
1시간넘게 뻘짓했는데 도저히 모르겠어서 포기하고 질문올렸다.
나중에수정예정
시발 걍 정신없어서 개짓거리한거
dfs로 푼 코드(완전탐색임)
import sysinput=sys.stdin.readlinen=int(input())answer=float("inf")
arr=[list(map(int, input().split())) for _ in range(n)]def get_score(team):
tmp=0 for i in team: for j in team: tmp+=arr[i][j]
return tmpdef dfs(start,team): global answer if len(team)==n//2:
other=[x for x in range(n) if x not in team]
answer=min(abs(get_score(team)-get_score(other)),answer) return
for i in range(start,n): dfs(i+1,team+[i]) dfs(0, [])
print(answer)