[백준 14899번] 스타트와 링크(파이썬)

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

14889번: 스타트와 링크

이 문제는 DFS로도 풀수는 있지만

일반적인 경우에는

시간초과가 발생합니다.

사실상 이 문제는

combination을 쓰라고

거의 유도한 문제에 가깝습니다.

 

#백준 14899번 스타트와 링크
from itertools import combinations

N=int(input())
graph=[list(map(int,input().split())) for _ in range(N)]
numbers=[i for i in range(N)]
answer=int(1e9)
#combiation으로 팀을 만드는 모든 경우를 받는다
for c in combinations(numbers,N//2):
    visited=[False]*N
    start=[]
    link=[]
    #스타트팀을 받는 경우
    for i in c:
        visited[i]=True
        start.append(i)
    #링크팀은 스타트팀으로 배정되지 않은 사람들을 배정
    for i in range(N):
        if not visited[i]:
            link.append(i)

    s_num=0
    l_num=0

    for i in range(N//2):
        for j in range(N//2):
            if i==j:
                continue
            s_num+=graph[start[i]][start[j]]
            l_num+=graph[link[i]][link[j]]
    n_an=abs(s_num-l_num)
    answer=min(answer,n_an)

print(answer)

문제의 난이도가 높고 낮고보다는

combination을 쓸줄 아는지 여부를 묻는 느낌이 컸습니다.

https://chldkato.tistory.com/155

백준 14889 스타트와 링크 (파이썬)

이런식으로 DFS로 풀이하는 경우도 있으니

공부에 참고하시면 도움이 되실 겁니다.