백준 스타트와 링크 [14889] 파이썬(Python) 코드 + 해설

백준 스타트와 링크 14889

문제 이해하기

이 문제는 브루트 포스와 백트래킹 관련 문제입니다.

해결 방법

• 팀 조합 생성: N명의 사람들 중 N/2명을 선택하여 한 팀을 구성하고, 나머지 N/2명은 다른 팀을 구성합니다.
• 능력치 계산: 각 팀에 대해 팀에 속한 모든 쌍의 사람들에 대해 능력치를 합산합니다.
• 차이 계산 및 최소화: 두 팀의 능력치 합의 차이를 계산하고, 그 중 최소값을 찾습니다.

구현 방법

1. 입력 받기
   • N과 능력치 행렬 SSS를 입력받습니다.
   • 사람의 번호는 0부터 N-1까지로 설정합니다.
2. 모든 팀 조합 생성
   • N명의 사람들 중 N/2명을 선택하는 모든 조합을 생성합니다.
   • itertools.combinations를 사용합니다.
   • 조합의 대칭성을 이용하여 전체 조합의 절반만 고려합니다.
3. 팀 능력치 합 계산
   • 각 팀 조합에 대해 다음을 수행합니다:
     • 팀 A의 능력치 합을 계산합니다.
       • 팀 A에 속한 모든 두 사람의 쌍 (i, j)에 대해 Sij+Sji + Sij​+Sji​를 합산합니다.
     • 팀 B는 전체 사람에서 팀 A를 제외한 나머지 사람들입니다.
     • 팀 B의 능력치 합도 동일한 방식으로 계산합니다.
4. 능력치 차이 계산 및 최소값 갱신
   • 두 팀의 능력치 합의 차이 diff를 계산합니다.
   • 최소 능력치 차이를 갱신합니다.
   • 능력치 차이가 0이면 더 이상 탐색하지 않고 종료합니다.
5. 결과 출력
   • 최소 능력치 차이를 출력합니다.

 

import sys
from itertools import combinations

input = sys.stdin.readline

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
people = [i for i in range(N)]
min_diff = float('inf')

# 모든 팀 조합 생성 (전체 조합의 절반만 고려)
team_combinations = list(combinations(people, N // 2))
half = len(team_combinations) // 2

for idx in range(half):
    team_A = team_combinations[idx]
    team_B = [x for x in people if x not in team_A]

    # 팀 A의 능력치 합 계산
    ability_A = 0
    for i, j in combinations(team_A, 2):
        ability_A += S[i][j] + S[j][i]

    # 팀 B의 능력치 합 계산
    ability_B = 0
    for i, j in combinations(team_B, 2):
        ability_B += S[i][j] + S[j][i]

    # 두 팀의 능력치 차이 계산
    diff = abs(ability_A - ability_B)
    if diff < min_diff:
        min_diff = diff
        if min_diff == 0:
            break

print(min_diff)

코드 설명

입력 처리

• N과 능력치 행렬 S를 입력받습니다.
• 사람 번호는 0부터 N-1까지입니다.

팀 조합 생성

• itertools.combinations를 사용하여 N명의 사람들 중 N/2명을 선택하는 모든 조합을 생성합니다.
• 전체 조합의 절반만 고려하기 위해 half = len(team_combinations) // 2로 설정합니다.
  • 이는 팀 A와 팀 B를 구분하지 않기 때문에 대칭성을 활용한 것입니다.

14889 스타트와 링크 정답

 

도움이 되셨다면 공감과 댓글 부탁드립니다.