백준: 14889 스타트와 링크

문제

14889번: 스타트와 링크

 

문제 풀이

 앞서 푼 문제들은 (15650 N과 M (2), 1759 암호 만들기) 조합을 구하거나, 조합을 만족하는 경우를 찾는 문제였다. 이 문제에서는 조합을 순차적으로 구하게 되면 대칭되는 성질을 활용하는 문제이다. 예를 들어 예제 입력1을 나눌 수 있는 조합을 순차적으로 나열하면 [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]이다. 여기서 알 수 있는 것은 [0, 1], [0, 2], [0, 3] [1, 2], [1, 3], [2, 3] 와 같이 (조합[i], 조합 [조합의 수 -i - 1])가 하나의 경우의 수를 만족한다는 것을 알 수 있다.

 

 따라서 문제는 다음과 같이 해결할 수 있다.

• N에 따른 팀의 조합을 DFS를 통해 구한다.

• 앞서 말한 조합이 대칭되는 성질을 이용하여, 스타트, 링크 팀에 대한 능력치를 계산한다.

• 차가 가장 작은 경우를 반환한다.

 

코드

from sys import stdin


def dfs(idx, depth):
    if depth == n // 2:
        case.append([*check])
        return

    for i in range(idx, n):
        if not i in check:
            check[depth] = i
            dfs(i, depth + 1)
            check[depth] = -1


def team_ability(idx):
    sum_ability = 0
    team = case[idx]
    for player in team:
        for other_player in team:
            if other_player == player:
                continue
            sum_ability += ability[player][other_player]
    return sum_ability


if __name__ == '__main__':
    case = []
    answer = 10 ** 7
    n = int(stdin.readline())
    idx = [i for i in range(n)]
    ability = [list(map(int, stdin.readline().split())) for _ in range(n)]
    check = [-1] * (n // 2)
    dfs(0, 0)
    print(case)

    for i in range(len(case) // 2):
        answer = min(answer, abs(team_ability(i) - team_ability(-i-1)))

    print(answer)

팀의 능력치를 계산 할때, if other_player == player는 생략해도 상관 없다. i, j가 같은 경우는 0이기 때문이다.