14889 스타트와 링크

문제

팀 N명이 시합을 하는데, 어떤 팀원과 팀을 할지에 따라 능력치가 다르다.
능력치 표가 주어질 때, 능력치 차이가 가장 적은 값을 찾는 문제이다.

문제 링크

코드

처음에 푼 코드

생각한 풀이법
1. 팀원 n명을 뽑는다 (combination)
2. 팀의 능력치를 계산한다.
3. answer를 갱신한다.

import sys
from itertools import combinations
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().strip().split())) for i in range(n)]
answer = 20 * 20 * 100 + 1

for T in combinations(range(n), n//2):
    team1 = []
    team2 = []
    for i in range(n):
        if i in T:
            team1.append(i)
        else:
            team2.append(i)

    power1 = 0
    power2 = 0
    for i in team1:
        for j in team1:
            power1 += arr[i][j]
    for i in team2:
        for j in team2:
            power2 += arr[i][j]
    answer = min(answer, abs(power1 - power2))
print(answer)

최대 시간은
combination(n, n//2) * (O(2n) + O(n x n) + O(n/2 x n/2)
-> nCn//2 x O(n^2)

n의 최댓값이 20이라 돌아가는 상황이었고, 다른 사람들의 코드를 보고 공부한 내용을 적어보려한다.

import sys
from itertools import combinations
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().strip().split())) for i in range(n)]
answer = 20 * 20 * 100 + 1

row_sum = [sum(i) for i in arr]
col_sum = [sum(col) for col in zip(*arr)]
stat_per_member = [i+j for i, j in zip(row_sum, col_sum)]
total_sum = sum(row_sum)

for stat in combinations(stat_per_member, n//2):
    score = abs(total_sum - sum(stat))
    answer = min(score, answer)
print(answer)

# python 에서 * unpaking의 역할을 한다
# row_sum과 같은 형태는 많이 봤겠지만
# col_sum의 경우는 처음 보는 것일 것이다

arr = [1,2,3]
# *arr => 1, 2, 3
# i, j, k = [*a]
# i = 1
# j = 2
# k = 3

zip() # 크키가 같은 두 배열을 합치는 역할을 한다.

arr = [(1,2), (3,4)]
zip(*arr) # => zip((1, 2), (3, 4)) => (1, 3) (2, 4)

# 이제 아래 두 코드가 이해가 될 것 이다.
row_sum = [sum(row) for row in arr]
col_sum = [sum(col) for col in zip(*arr)]

# stat_per_member
stat_per_member = [i+j for i, j in zip(row_sum, col_sum)]

두 row_sum과 col_sum을 합친 모습을 링크에 있는 그림으로 설명하자면 이런 모양이 된다.

전체합에서 이제 combination()에서 고른 원소를 빼면,
특정 원소가 두번씩 빠지게 된다.
즉 1,2를 골랐을 때,

빨간색으로 칠해진 원소는 두번씩 빠지고 안칠해진 부분은 그대로 남아 있게 되는데
안칠해진 부분 | 빨간색 칠해진 부분이 각각 팀들의 점수 합이된다.