문제
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.
문제 정리
- N 명을 입력받고 N은 무조건 짝수이다.
- N을 두 팀으로 나눈다.
- N*N 행렬이 주어지고 i 번 사람과 j 번 사람이 같은 팀에 속했을 경우에 팀에 더해지는 능력치가 있다.
- Start팀과 Link팀의 능력치 차이를 최소화시켜야한다.
- 모든 경우의 수를 탐색해야 하는 Brute force 문제이다.
- 재귀로 풀되 두 팀의 차이가 최소인 값을 출력해야한다.
- 같은 사람이 다른 팀에 들어가 있지 못한다는 점을 유의해야한다.
- 모든 사람은 두가지 경우가 있다. 스타트팀에 있는 경우와 링크팀에 있는 경우이다.
문제 풀이
첫 번째 풀이
# 시간초과 코드 - 많은 중복이 발생.
import sys
input = sys.stdin.readline
n = int(input())
ability = [list(map(int, input().split())) for _ in range(n)]
# 모든 조합의 팀을 구성
def make_team(ability, n, start, link, result, idx):
sl = len(start)
ll = len(link)
# 양 팀의 팀원의 수가 전체 인원 수가 된다면
if sl + ll == team_n*2:
sa = 0
la = 0
for i in start:
for j in start:
sa += ability[i][j]
for i in link:
for j in link:
la += ability[i][j]
result.append(abs(sa-la))
return
if len(start) != team_n:
start.append(idx)
make_team(ability, n, start, link, result, idx+1)
start.pop() # 해당 팀원이 start팀에 포함되지 않은 경우 추가
if len(link) != team_n:
link.append(idx)
make_team(ability, n, start,link,result,idx+1)
link.pop() # 해당 팀원이 link팀에 포함되지 않은 경우 추가
return min(result)
team_n = int(n/2)
print(make_team(ability, team_n, [], [], [], 0))첫 번째 풀이 중 크리티컬하게 시간초과가 나는 부분은 총 두가지이다.
-
result에 능력치 차이 값을 담고 다시 min(result)로 탐색을 진행한다는 점
최소값을 계속 업데이트 하는 방식으로 바꾼다면 append하는 시간을 줄일 수 있다. -
start팀과 link팀을 따로 구한다는 점
한 팀은 다른 팀의 팀원이 정해지는 순간 이미 정해지기에 start나 link를 기준으로 하여 다른 팀의 팀원을 구하면 된다.
두 번째 풀이
위의 오류를 고치는 방향으로 다시 문제에 접근하였다.
import sys
input = sys.stdin.readline
n = int(input())
ability = [list(map(int, input().split())) for _ in range(n)]
# 한팀만 재귀 돌리고 나머지는 다른 팀에 의해 팀이 결정되는 방식으로 진행
def make_team(ability, n, start, idx, min_diff):
if len(start)*2 == n:
sa = 0
la = 0
# start팀이 아닌 플레이어는 link팀이다.
link = [i for i in range(n) if i not in start]
# 각 팀별로 능력치합 구하기
for i in start:
for j in start:
sa += ability[i][j]
for i in link:
for j in link:
la += ability[i][j]
# 최소값 구하기
return min(min_diff, abs(sa-la))
if idx < n: # 플레이어의 수는 0~n-1까지 존재
start.append(idx) # 해당 팀원을 넣은 경우
min_diff = make_team(ability, n, start, idx+1, min_diff)
start.pop() # 해당 팀원을 넣지 않은 경우
min_diff = make_team(ability, n, start, idx+1, min_diff)
# 최종 최소값 반환
return min_diff
# 함수의 인자를 활용하여 최소값 탐색
min_diff = make_team(ability, n, [], 0, float('inf'))
print(min_diff)하지만 아직도 문제가 있다.
만약 플레이어가[1,2,3,4]이고
start팀이 [2,3]
link팀이 [1,2]인 경우와
link팀이 [2,3]
start팀이 [1,2]
이 둘의 경우의 결과는 같기에 중복인 경우의 수를 구하게 됐다. 위의 답도 물론 정답처리는 받았지만 이를 절반의 경우의 수 탐색을 줄일 수 있다. 꽤나 아슬아슬하게 테스트케이스를 통과 받은 듯 하다.
이 문제는 나중에 해결해 보아야겟다...ㅠ
