*문제 출처는 백준에 있습니다.
문제 제목: 스타트와 링크 / 14889번 (실버 1단계)
문제 사이트: https://www.acmicpc.net/problem/14889
문제 설명

나의 풀이
from itertools import combinations
def solution():
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
min_diff = int(1e9)
# 가능한 팀 조합 절반만 순회
people = list(range(n))
for team1 in combinations(people, n // 2):
team2 = list(set(people) - set(team1))
# 팀 능력치 계산
def team_score(team):
score = 0
for i in team:
for j in team:
if i != j:
score += arr[i][j]
return score
diff = abs(team_score(team1) - team_score(team2))
min_diff = min(min_diff, diff)
if min_diff == 0:
break # 최적값 조기 종료
print(min_diff)
if __name__=="__main__":
solution()

※ 알아야 할 것
예를 들어서 [0, 1]이 team 1일 때 team2 팀에는 [0, 1]이 들어가면 안됩니다!
| [0,1] | [2,3] | 서로 겹치지 않음 |
| [0,2] | [1,3] | 서로 겹치지 않음 |
| [0,3] | [1,2] | 서로 겹치지 않음 |
| [0,1] | [0,2] | 0번이 겹침 |
| [1,2] | [2,3] | 2번이 겹침 |
from itertools import combinations
print(list(combinations([0,1,2,3], 2)))
# 결과 [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 빵집 / 3109번 / Python (0) | 2025.05.06 |
|---|---|
| 백준 / 경로 찾기 / 11403번 / Python (0) | 2025.05.05 |
| 백준 / 내려가기 / 2096번 / Python (0) | 2025.05.01 |
| 백준 / 트리 순회 / 1991번 / Python (0) | 2025.04.30 |
| 백준 / 상자넣기 / 1965번 / Python (0) | 2025.04.30 |