[백준] 15661번: 링크와 스타트

문제

백준 - 15661번: 링크와 스타트

분석

N명의 사람이 스타트 팀과 링크 팀으로 나뉘어 축구를 한다. 각 팀은 1명 이상이어야 한다.
S는 같은 팀이 됐을 때 팀에 보탤 수 있는 능력치를 나타내는 행렬이며, Sij와 Sji는 다를 수 있다.
두 팀으로 나눴을 때, 가장 두 팀의 능력치 차이가 작을 경우를 구하는 문제이다.

기본 조합 문제에서는 n개 중 몇 개를 선택해야 하는 지가 정해져있었다. 이 문제는 그게 정해지지 않았기 때문에 최소 팀인원인 1부터 n의 절반까지 뽑는 것으로 범위를 정했다.
n의 절반까지만 한 이유는 결과적으로 start team과 link team의 능력 차이를 묻는 것이므로 정확히 어디 팀에 누가 뽑히는 지는 중요하지 않다.
start team에서 절반 이상 뽑는 행위는 link team에서 절반 이상 뽑았던 경우와 일치하기 때문에 무의미하다.

팀 능력치 차이는 team_link라는 team_start에 속하지 않는 것들을 넣은 리스트를 만들었고,
각각의 능력치를 구하고 차이를 구했다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
S = [
    list(map(int, input().split()))
    for _ in range(n)
]

def calGap(team_start):
    skill_start = 0
    for i in team_start:
        for j in team_start:
            skill_start += S[i][j]
    team_link = [i for i in range(n) if i not in team_start]
    skill_link = 0
    for i in team_link:
        for j in team_link:
            skill_link += S[i][j]
    return abs(skill_start-skill_link)

def combi(i, cnt, sub_n):
    global mn
    if cnt == sub_n:
        gap = calGap(team_start)
        mn = min(mn, gap)
        return
    if i == n:
        return
    team_start.append(i)
    combi(i+1, cnt+1, sub_n)
    team_start.pop()
    combi(i+1, cnt, sub_n)

mn = sys.maxsize
for sub_n in range(1, n//2+1):
    team_start = []
    combi(0, 0, sub_n)
print(mn)

끝으로..

조합, 백트래킹 문제에서 살짝 응용한 문제를 풀어봤다.
python으로 안 풀리고 pypy로 풀리는 경우가 좀 있다.
그러나 누군가는 python으로도 풀었기에 나중에 python 으로도 다시 도전 해봐야겠다.