[알고리즘][Python] 백준 14889 스타트와 링크 문제 풀이

문제 출처 : www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

문제 해석 : 두 팀으로 나누어서 능력치 차이를 최소로 하게 팀을 구성하는 문제이다.

 

문제 풀이 : 처음에는 itertools의 permutations를 이용해서 풀려고 했지만 메모리초과가 나와서 직접 팀을 구성하고 이를 계산해서 풀었다. 풀이에 필요한 기능은

 

1. 팀을 구성하는 함수

2. 팀의 능력치 차이를 계산하는 함수

 

가 있으며 이를 활용해서 바로 풀어 낼 수 있다.

---

풀이 코드

def cal_diff(team1, team2):
    sum_team1 = 0
    sum_team2 = 0

    for i in range(len(team1)):
        for j in range(len(team1)):
            sum_team1 += arr[team1[i]][team1[j]]
            sum_team2 += arr[team2[i]][team2[j]]

    return abs(sum_team1 - sum_team2)

def make_team(team1, count, N, start):
    global answer

    if count == N//2:
        team2 = []
        for i in range(N):
            if i not in team1:
                team2.append(i)

        local_diff = cal_diff(team1, team2)
        answer = min(answer, local_diff)
        return

    for i in range(start, N):
        if i not in team1:
            team1.append(i)
            make_team(team1, count+1, N, i+1)
            team1.remove(i)

if __name__=="__main__":
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    answer = int(1e9)
    make_team([], 0, N, 0)

    print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.