[백준/BOJ] #14889 스타트와 링크.python(파이썬)

문제 링크 / 출처

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

문제 요약

주어진 인원을 반으로 나눴을 때 각 팀의 능력치 점수합의 최소 차이를 구하는 문제.

[제약사항]

4 ≤ N ≤ 20, N은 짝수

• S_ii는 항상 0
• 나머지 S_ij는 1보다 크거나 같고, 100보다 작거나 같은 정수

 

풀이

어떤 두 사람이 같은 팀일 때 더해지는 능력치 시너지 점수가 주어진다.

이 그림에서 1,3을 A팀이라 하고 2,4를 B팀이라 하면, 서로중복되는 부분(파란색)은 뺄셈 연산으로 사라지므로

 

A팀의 능력치 점수 합 - B팀의 능력치 점수 합 == A팀 번호의 세로합(빨간색) - B팀 번호의 가로합(초록색)

 

가 된다.

 

따라서 A팀을 N//2명 뽑은 뒤 세로합더해주고, 나머지(B팀)의 가로합을 빼주면 양 팀의 능력치 점수의 차이를 알 수 있게 된다.

 

위와 같은 방식으로 재귀함수를 이용해 N명의 선수중에서 N//2명의 선수를 뽑아 양 팀의 능력치 점수 차이를 계산해주었다.

 

코드

# 스타트와 링크.
import sys
input = sys.stdin.readline


def select(_cnt, _idx=0):   
    global min_val
    if _cnt == N//2:            # 절반을 뽑은 경우
        temp_val = 0            # 두팀의 능력치 차이를 저장할 임시변수
        for i in range(N):
            if check[i]:              # 두팀의 능력치 차이를 구해야하므로,
                temp_val += v_sum[i]  # A팀의 점수는 더하고
            else:
                temp_val -= h_sum[i]  # B팀의 점수는 빼줘서 차이를 구한다.
        if min_val > abs(temp_val):   # 두 팀의 능력치 차이가 최소인 경우
            min_val = abs(temp_val)
        return

    for i in range(_idx, N):    # 전체인원에서 A팀을 뽑음(조합)
        check[i] = True
        select(_cnt+1, i+1)     # 조합으로 뽑아야하므로, 현재까지 뽑은 인원 수와 인덱스를 넘겨줌
        check[i] = False


N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
v_sum = [0]*N
h_sum = [0]*N
check = [False]*N   # A팀은 True, B팀은 False로 지정

for r in range(N):
    for c in range(N):
        v_sum[c] += arr[r][c]   # A팀의 능력치 점수(세로합)
        h_sum[r] += arr[r][c]   # B팀의 능력치 점수(가로합)

min_val = 9876543210    # 최솟값을 구해야하므로 충분히 큰 값으로 지정
select(0)               # 재귀함수 실행
print(min_val)