백준 14889 스타트와 링크

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

14889번: 스타트와 링크

 

맨처음에 itertools로풀었다.

굳이 모든 콤비에 대하여 다 구할 필요 없이, 

콤비의 반만 계산하면 나머지는 스타트와 링크가 바뀐 경우이므로,

반만 계산한다.

from itertools import combinations
import sys
input=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+10
for 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=tmp

print(answer)

문제는 dfs로 풀 때 정답코드를 변수명만 다르게해서 배껴도 문제가 생긴다는 점이다.

1시간넘게 뻘짓했는데 도저히 모르겠어서 포기하고 질문올렸다.

나중에수정예정 

시발 걍 정신없어서 개짓거리한거

dfs로 푼 코드(완전탐색임)

import sys

input=sys.stdin.readline

n=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 tmp

def 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)