[Baekjoon] 14889번 - 스타트와 링크

 

14889번: 스타트와 링크

두 팀으로 인원을 나누고 팀 능력치의 차이가 최소가 되도록 하는 프로그램을 구현해라

 

문제 풀이

1) 조합으로 a팀을 고를 수 있는 경우의 수를 모두 구한다.

2) 모든 사원 집합에서 a팀을 제외하여 (차집합) b팀을 구한다.

3) a팀의 합과 b팀의 합을 구하고 차를 계산한다.

4) 최소값을 구해 출력한다.

 

 

코드

from itertools import combinations

def solution():
    global min_value
    for team_a in combinations(members, n//2):
        team_b = list(set(members) - set(team_a))
        answer = calculate_diff(team_a, team_b)
        min_value = min(min_value, answer)
    

def calculate_diff(team_a, team_b):
    sum_ability_a, sum_ability_b = 0, 0
    for i in range(n//2):
        for j in range(i, n//2):
            sum_ability_a += (chemi[team_a[i]][team_a[j]] + chemi[team_a[j]][team_a[i]])
            sum_ability_b += (chemi[team_b[i]][team_b[j]] + chemi[team_b[j]][team_b[i]])
    return abs(sum_ability_a - sum_ability_b)

n = int(input())
members = [i for i in range(n)]
chemi = []
for _ in range(n):
    chemi.append(list(map(int, input().split())))
min_value = 1e9
solution()
print(min_value)

 

느낀점

차집합을 이용해 b팀을 구하는 방식이 더 빠르다.

그리고,, 조합을 이용하면 될 것을 굳이굳이 팀을 직접 짜줬는데 그러지말자,,,itertools를 사랑하자

 

✍ 나의 뻘짓 기록

 

def divide_team(count, team_a, start):
    global min_value

    if count == n//2:
        team_b = list(members - set(team_a))
        answer = calculate_diff(team_a, team_b)
        min_value = min(min_value, answer)
        return

    for i in range(start, n):
        if i not in team_a:
            team_a.append(i)
            divide_team(count+1, team_a, start+1)
            team_a.remove(i)

def calculate_diff(team_a, team_b):
    sum_ability_a, sum_ability_b = 0, 0
    for i in range(n//2):
        for j in range(i, n//2):
            sum_ability_a += (chemi[team_a[i]][team_a[j]] + chemi[team_a[j]][team_a[i]])
            sum_ability_b += (chemi[team_b[i]][team_b[j]] + chemi[team_b[j]][team_b[i]])
    return abs(sum_ability_a - sum_ability_b)

n = int(input())
members = set(range(0, n))
chemi = []
for _ in range(n):
    chemi.append(list(map(int, input().split())))
min_value = 1e9
divide_team(1, [0], 1)
print(min_value)