[python] 백준 - 14889. 스타트와 링크

🤔문제 해결

• S3 | 브루트포스, 백트래킹

재귀 함수를 이용하여 A팀을 구한다.

• 전체 멤버의 절반이 될 때까지 팀을 구성

• set으로 구한다. ( 교집합을 사용해서 B팀을 구하기 위해 )

두 팀을 구했으면 각 팀의 모든 조합을 테이블에서 값을 계산해서 구해준다

• 이번에는 콤비네이션 모듈을 사용했다.

• 테이블의 값을 모두 더해주고

• 두 팀의 총합을 빼준뒤 절대값을 씌워서 차이를 구한다.

최소값으로 답을 갱신해준다.

 

💨 팀을 구할 때 콤비네이션을 쓰지 않은 이유는 콤비네이션은 모든 경우의 수를 구하기 때문

전체 회원 [0, 1, 2, 3] 일 때

A 팀이 0,1 B팀이 1,2 인 경우와

A 팀이 2,3 B팀이 0,1 인 경우의 답은 같지만

콤비네이션은 이 두가지 경우를 구하므로 비효율적

💻소스 코드

from itertools import combinations


# 팀 나누기 - set 이용
def split_team(a_team, idx):
    global answer
    if len(a_team) == len(all_team) // 2:
        b_team = all_team - a_team
        answer = min(answer, abs(sum_stat(a_team) - sum_stat(b_team)))
        return

    for i in range(idx, len(all_team)):
        a_team.add(i)
        split_team(a_team, i + 1)
        a_team.remove(i)


# 팀 스탯 계산하기
def sum_stat(team):
    stat = 0
    for player1, player2 in combinations(team, 2):
        stat += table[player1][player2] + table[player2][player1]

    return stat


if __name__ == '__main__':
    N = int(input())
    table = [list(map(int, input().split())) for _ in range(N)]
    all_team = set(i for i in range(N))
    answer = float('inf')

    split_team(set(), 0)

    print(answer)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

14889번: 스타트와 링크