[BOJ] 14889 스타트와 링크

poiu8944·2020년 6월 30일
0

알고리즘

목록 보기
5/8

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

오랜만에 알고리즘을 올리는 것 같다. 많은 문제를 올리는 것보다 오랜 시간 생각해서 풀었거나, 알고리즘 스킬(?)을 배운 것만 올리기로 했다. (올리고 싶거나 기록이 필요하다 생각될 때 올려야지 :)

itertools를 사용하지 않고 직접 풀려고 시도했는데 실패했다.. dfs로 구현했다가 시간 초과가 계속 발생하여 결국 itertools를 사용하여 풀었다.

가능한 팀의 조합의 절반을 나눌 때 0번째 선수를 포함하는 조합만 남도록 하였는데, 0번째 선수가 team_A에 속해있지 않다면 team_B에 반드시 속하기 때문에 상관없다. 아니, 중복된 계산을 피하기 위해 반드시 반으로 나눠야 하는데, 기준이 반드시 0번째 선수가 아니어도 된다.

set을 사용하였는데, set은 집합 연산을 할 수 있어 굉장히 편리하다. 팀을 나눌 때 차집합으로 구하고 싶어 사용하였다.

import sys, itertools
input = sys.stdin.readline
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

answer = 999999
teams = itertools.combinations(range(N), N//2) # 가능한 팀의 조합
teams = filter(lambda x:0 in x,teams) # 모든 가능한 팀의 조합의 절반 (0번째 선수를 포함하는 조합)

for team in teams:
    team_A = set(team)
    team_B = set(range(N))-set(team)
    team_A_score = 0
    team_B_score = 0
    for (i, j) in itertools.permutations(team_A, 2):
        team_A_score += arr[i][j]
    for (i, j) in itertools.permutations(team_B, 2):
        team_B_score += arr[i][j]
    answer = min(answer, abs(team_A_score-team_B_score))

print(answer)

0개의 댓글