•
문제 설명
인원 N명과, 1 ~ N 까지 각 인원의 쌍(i, j)의 능력치가 작성된 표(S)가 주어진다.
이때 한팀당 N/2 명으로 두 팀으로 인원을 나누어 각 팀의 능력치의 차이가 최소가 되도록 만든다.
이때 팀의 능력치는 아래와 같이 구한다.
팀원이 x, y, z 일 때, 각 팀원의 쌍 ( [x, y], [x, z], [y, z] … )의 능력치를 모두 더한다.
팀원 쌍(x, y)의 능력치는 이다. 이때 와 는 다를 수 있으니 주의해야한다.
•
풀이 방법
우선 두 팀의 인원이 동일하기 때문에, 한팀만 구하면 나머지팀의 인원은 자동으로 결정된다.
따라서 한팀은 재귀로, 나머지 팀은 한팀이 다 구해지면 나머지 값을 사용하면 된다.
이때 재귀로 구하는 팀은 N명에서 N/2명을 중복을 허락하지 않는 순열로 구해야한다.
중복을 허락하면 [3, 2, 1] / [1, 2, 3] 구성도 다른 팀으로 인식한다.
이렇게 되면 시간초과가 발생한다.
본인은 팀원 번호가 오름차순일때만 추가되도록 조건을 추가했다.
두 팀 모두 인원이 구성이 되면 각 팀의 점수를 구하여 비교 후, 최소값일때만 갱신한다.
이 문제는 팀원이 모두 구성이 되어야 점수를 구할 수 있기 때문에, 팀원이 구성되기 전에 최솟값을 비교하여 팀 구성 자체를 중단할 수는 없다.
•
성공 코드
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
# 최소 값 저장
min_value = float("inf")
# 스타트팀 저장(링크로 해도됨)
start_team = []
# 팀의 점수 구하기
def get_team_sum(team):
team_sum = 0
for i in range(len(team)):
for j in range(i + 1, len(team)):
# S_ij + S_ji
team_sum += board[team[i]][team[j]] + board[team[j]][team[i]]
return team_sum
def dfs(depth):
global min_value
# start_team 구성이 완료된경우
if depth == N // 2:
link_team = []
# start_team에 없는 인원은 모두 link_team
for i in range(N):
if i not in start_team:
link_team.append(i)
# start_team과 link_team 점수를 비교
start_team_score = get_team_sum(start_team)
link_team_score = get_team_sum(link_team)
if abs(start_team_score - link_team_score) < min_value:
min_value = abs(start_team_score - link_team_score)
return
# start_team 구성
for i in range(N):
if i not in start_team:
# 중복되지 않는 start_team을 구성
# [3, 2, 1], [1, 2, 3] 와 같이 중복 방지
# 오름차순으로만 구성되도록 만든다.
if len(start_team) > 0 and i <= start_team[-1]:
continue
start_team.append(i)
dfs(depth + 1)
start_team.pop()
dfs(0)
print(min_value)
Python
복사