1. 문제
2. 풀이
코드
import itertools
n = int(input())
abilities = [list(map(int, input().split())) for _ in range(n)]
players = [num for num in range(n)]
start_teams = list(itertools.combinations(players, n//2))
min_diff = float('inf')
for start_team in start_teams:
link_team = tuple(player for player in players if player not in start_team)
start_sum = sum(abilities[i][j] + abilities[j][i] for i, j in itertools.combinations(start_team, 2))
link_sum = sum(abilities[i][j] + abilities[j][i] for i, j in itertools.combinations(link_team, 2))
min_diff = min(min_diff, abs(start_sum - link_sum))
print(min_diff)입력 및 출력
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
>> 03. 로직
-
입력으로 선수의 수 n을 받는다.
-
abilities 리스트에 능력치 행렬을 입력받는다. 각 행은 플레이어의 능력치를 나타내며, abilities[i][j]는 i번 플레이어와 j번 플레이어의 능력치를 의미한다.
-
players 리스트에는 선수의 번호를 저장한다. 예를 들어, n이 4이면 players는 [0, 1, 2, 3]이 된다.
-
입력으로 받은 팀의 인원 수 n을 기준으로 가능한 모든 팀 조합을 start_teams에 저장한다. 이 때,
combinations함수를 사용하여 팀을 구성한다. 각 팀은 n//2명으로 구성되어야 하므로 n의 절반에 해당하는 인원을 선택한다.
-
각 팀 조합인 start_team에 대해 다음 과정을 수행한다.
- 남은 플레이어들로 구성되는 link_team을 만든다. link_team은 players 리스트에서 start_team에 속하지 않은 플레이어들로 구성된다.
- start_team의 능력치 합 start_sum과 link_team의 능력치 합 link_sum을 계산한다. 이때,
combinations함수를 사용하여 팀 내에서 가능한 모든 능력치 조합을 계산한다.
min_diff와 abs(start_sum - link_sum) 중 작은 값을 min_diff로 업데이트한다.
-
모든 팀 조합에 대해 위의 과정을 반복하면서 최솟값 min_diff를 구한다.
-
최종적으로 min_diff를 출력한다.
4. 사용된 함수
combinations
파이썬에서 조합(Combination)을 생성하려면 itertools 모듈의 combinations 함수를 사용할 수 있다. combinations 함수는 주어진 iterable에서 지정된 크기의 모든 조합을 생성하는 이터레이터를 반환한다.
코드
from itertools import combinations
# 리스트의 조합 생성
lst = [1, 2, 3, 4]
k = 2 # 선택할 요소의 개수
comb = combinations(lst, k)
# 조합 출력
for c in comb:
print(c)
결과
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)위의 코드에서 combinations(lst, k)는 리스트 lst에서 크기 k의 모든 조합을 생성하는 이터레이터를 반환한다. 이후 for 루프를 통해 각 조합을 출력한다.
permutations
파이썬에서 순열(Permutation)을 생성하려면 itertools 모듈의 permutations 함수를 사용할 수 있다. permutations 함수는 주어진 iterable에서 모든 순열을 생성하는 이터레이터를 반환한다.
코드
from itertools import permutations
# 리스트의 순열 생성
lst = [1, 2, 3]
perm = permutations(lst)
# 순열 출력
for p in perm:
print(p)
결과
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)위의 코드에서 permutations(lst)는 리스트 lst의 모든 순열을 생성하는 이터레이터를 반환한다. 이후 for 루프를 통해 각 순열을 출력한다.
순열(Permutation)과 조합(Combination)의 차이
1. 순서의 유무:
- 순열(Permutation): 순열은 원소의 순서를 고려하여 구성된다. 다시 말해, 같은 요소들이라도 순서가 다르면 서로 다른 순열로 간주된다. 예를 들어, [1, 2]와 [2, 1]은 다른 순열이다.
- 조합(Combination): 조합은 원소의 순서를 고려하지 않고 구성된다. 따라서 같은 요소들로 이루어진 조합이라면 순서에 관계없이 동일한 조합으로 간주된다. 예를 들어, [1, 2]와 [2, 1]은 동일한 조합이다.
2. 중복 여부:
- 순열(Permutation): 순열은 동일한 요소를 중복해서 사용할 수 없다. 각 요소는 한 번씩만 포함된다.
- 조합(Combination): 조합은 동일한 요소를 중복해서 사용할 수 있다. 같은 요소를 여러 번 선택하여 조합을 구성할 수 있다.
3. 계산 방법:
- 순열(Permutation): 순열은 원소의 개수에 따라 경우의 수가 크게 증가하기 때문에, 일반적으로 재귀적인 방법이나 반복적인 방법을 사용하여 계산된다.
- 조합(Combination): 조합은 순열보다 계산이 간단하다. 이항 계수(Binomial Coefficient)를 활용하여 조합의 수를 계산하는 경우가 많다.
