문제

N(짝수) 명의 사람들을 스타트, 링크 팀으로 나누어 배정
팀에 i와 j가 소속되면 팀에 더해지는 능력치는 Sij + Sji
각각의 능력치들을 합하면 팀의 능력치
스타트 팀과 링크 팀의 능력치 차가 최소가 되도록 사람들을 분배하자.

입력과 출력

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

문제 해결 요약

코드 설명

import 및 입력받기

from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input())
teams = set([i for i in range(n)])
power = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    power.append(tmp)

인원 수 입력받고
인원 리스트를 만들어 준다 teams
power에 능력치들을 입력받음

스타트 팀과 링크 팀 능력치 계산

스타트 팀과 링크 팀의 능력치를 계산해 둘의 차가 최소가 되는 값을 구한다

team_s = 0
team_l = 0
diff = 1000000
for combi in combinations(teams, int(n/2)):
    team_s = total(combi)
    team_l = total(teams - set(combi))
    diff = min(diff, abs(team_s-team_l))

인원을 임의로 반으로 나눠줌
스타트 팀에 사용한 인원은 링크 팀에 들어가지 않도록 team - set(combi)
스타트 팀과 링크 팀 각각의 능력치를 계산
차를 구해 최솟값이면 diff를 갱신해줌

팀 능력치 계산 함수 정의

팀의 능력치를 계산하는 함수를 정의해준다

def total(combis):
    tmp = 0
    for c in combinations(combis, 2):
        tmp += (power[c[0]][c[1]] + power[c[1]][c[0]])
    return tmp

팀원 조합에 대해 2명씩 조합을 구한다
두 명의 능력치를 계산해 tmp에 더해준다
total 리턴

전체 코드

from itertools import combinations
import sys
input = sys.stdin.readline

def total(combis):
    tmp = 0
    for c in combinations(combis, 2):
        tmp += (power[c[0]][c[1]] + power[c[1]][c[0]])
    return tmp

n = int(input())
teams = set([i for i in range(n)])
power = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    power.append(tmp)

team_s = 0
team_l = 0
diff = 1000000
for combi in combinations(teams, int(n/2)):
    team_s = total(combi)
    team_l = total(teams - set(combi))
    diff = min(diff, abs(team_s-team_l))

print(diff)

728x90