BOJ14889 스타트와 링크

leehe228·2021년 8월 18일
0
post-thumbnail

문제

BOJ14889 스타트와 링크
실버III | 백준 14889 | Python3 파이썬 풀이


알고리즘

  1. Python itertools를 이용해 가능한 팀의 모든 조합 리스트를 생성한다.
  2. 각 조합에서 A, B 팀의 능력치의 합을 계산한다.
  3. A, B 팀의 능력치의 합의 차이 중 최솟값을 저장한다.
  4. 최솟값을 출력한다.

코드

import sys
from itertools import combinations

input = sys.stdin.readline

N = int(input())
# 능력치 정보
table = [list(map(int, input().split())) for _ in range(N)]
nums = [i for i in range(N)]

# 가능한 팀의 모든 조합
combs = [i for i in list(combinations(nums, N // 2))]

minv = sys.maxsize

for i in range(len(combs) // 2):
    teamA = combs[i]
    teamB = combs[-1 - i]
	
    # A팀 가능한 조합의 능력치 합
    scoreA = 0
    for j in range(N // 2):
        for k in teamA:
            scoreA += table[teamA[j]][k]
	
    # B팀 가능한 조합의 능력치 합
    scoreB = 0
    for j in range(N // 2):
        for k in teamB:
            scoreB += table[teamB[j]][k]
	
    # 두 팀 능력치 합의 최솟값을 저장
    minv = min(minv, abs(scoreA - scoreB))

print(minv)

결과

profile
건국대학교 컴퓨터공학부 이호은 | 알고리즘 정리 블로그

0개의 댓글