[Python] 백준 14889 스타트와 링크

 

문제 분석

• 짝수 n
• n/2 씩 스타트팀 & 링크 팀 : 각 팀 인원수는 같음
• 능력치 Sij
• 스타트 팀의 능력치와 링크 팀의 능력치 차이 최소화
• 자기자신은 같은팀이 될 수 x
• (i,j) : (1,2)와 (2,1)이 값이 다르지만 능력치는 이 둘의 합
• 숫자 2쌍 씩 선택이 되는데 순서 다르게 해서 합을 구해야 능력치가 나옴
• N/2명씩

 

코드 설계

• 서로 다른 N명을 2팀으로 나누기 : 서로 다른 n명 중 중복을 허용하지 않고, n/2명 고르기
• combination : nC(n/2)
• 한 팀을 고르면 다른 팀은 자동으로 설정됨
• combination에 들어 있는 n//2 중 2명씩 순서있는 조합을 나열하여 각 조합의 능력치 구하기
• (중복x, 순서o : 순열)
• 해서 최종적인 팀의 능력치를 구하고
• 각 팀에 대해 능력치 계산 하여 차 비교
• → min값 구하기

• combination의 i값에 대한 함수를 만들고 (team_start), 전체 인원에 대한 함수를 돌면서 team_start에 없는 인덱스이면 team_link

 

import sys
from itertools import combinations
input = sys.stdin.readline

n = int(input())
capacity = [list(map(int, input().split())) for _ in range(n)]
people = []
team_start = []
team_link = []

for i in range(n) : # 전체 인원 n명에 대한 index
    people.append(i)

for i in combinations(people, n//2) :
    team_start.append(i)

print(team_start)

실패..

 

정답 및 해설

1. 백트래킹(dfs)

참고 : https://chaeyami.tistory.com/230

• 방문 횟수가 전체 인원의 1/2이 될 때까지 방문
• 인원이 n/2로 나뉘었을 때, 각 팀의 능력치를 구하고 차의 최솟값 구하기

import sys
input = sys.stdin.readline

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

v = [False] * n
result = sys.maxsize # 큰 수로 초기화

def dfs(depth, idx) :
    global result

    if depth == n//2 : # 인원이 반반으로 나뉘면
       # 각 팀 능력치 초기화
       team_start = 0
       team_link = 0

       for i in range(n) :
          for j in range(n) :
             # 방문한 반을 start 팀으로 배정
             if v[i] and v[j] :
                team_start += status[i][j]
             # 방문하지 않은 반은 link 팀 배정
             elif not v[i] and not v[j] :
                team_link += status[i][j]

       result = min(result, abs(team_start-team_link))
       return

    else : # 인원이 안나눠져있다면
       for i in range(idx, n) :
          if not v[i] :
             v[i] = True
             dfs(depth+1, idx+1)
             v[i] = False

dfs(0,0)
print(result)

• 백트래킹으로 절반만 탐색하면 된다.
• 절반을 방문했다면, 나머지는 다른 팀으로 설정

• v의 크기 : n
• v는 팀을 나누기 위한 변수
• depth : 팀에 할당된 사람 수
• idx : 다음에 팀을 나눌 때, 어디부터 탐색할지 결정
• for i in range(idx, n) : 팀을 나누는 중이라면, idx부터 시작해서 남은 사람들을 팀에 배정
• 아직 팀에 속하지 않은 사람 (if not v[i])을 한 명씩 팀 Start에 배정하고 (v[i] = True), 이후 다시 재귀적으로 나머지 사람들을 팀에 할당
• 재귀가 끝나면, 다시 팀 배정을 취소하고 (v[i] = False) 다른 사람을 선택하는 방식으로 백트래킹 진행

// 시간초과..

 

2. 조합

참고 1 : https://edder773.tistory.com/117

참고 2 : https://velog.io/@min-ji99/%EB%B0%B1%EC%A4%80-14889-%EC%8A%A4%ED%83%80%ED%8A%B8%EC%99%80-%EB%A7%81%ED%81%AC

import sys
from itertools import combinations
input = sys.stdin.readline

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

# 순서o, 중복x : 순열을 통해 팀을 두 팀으로 나눔
teams = list(combinations(people, (n//2)))
result = sys.maxsize

# 두 팀의 능력 차이 계산
for team in teams :
    team_start = 0
    team_link = 0

    for i in team : # 순열로 만들어진 팀에 포함된 사람들 능력치 계산
        for j in team :
            team_start += status[i][j]

    not_team = [x for x in range(n) if x not in team]
    for i in not_team :
        for j in not_team :
            team_link += status[i][j]

    result = min(result,abs(team_start-team_link))

print(result)