[BOJ][⚪2][백준#14889] 스타트와 링크

문제 출처

BAEKJOON Online Judge #14889

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j 1 2 3 4

1   1 2 3

2 4   5 6

3 7 1   2

4 3 4 5  

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

스타트 팀: S12 + S21 = 1 + 4 = 5 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

스타트 팀: S13 + S31 = 2 + 7 = 9 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제

예제 1

입력

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

출력

0

예제 2

입력

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

출력

2

예제 3

입력

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

출력

1

My Sol

from itertools import combinations

def foo(team):
    ssum = 0
    for i in team:
        for j in team:
            ssum += mat[i][j]
            ssum += mat[j][i]
    return ssum//2


N = int(input())
mat = [list(map(int, input().split())) for _ in range(N)]
minDiff = 0xfffff
for comb in combinations(range(N), N//2):
    teamA = set(comb)
    teamB = set(range(N)) - teamA
    minDiff = min(minDiff, abs(foo(teamA) - foo(teamB)))

print(minDiff)

itertool에 의한 조합으로 teamA와 teamB의 두 그룹으로 나눌 수 있는 모든 경우에 대하여 각 팀의 능력치 합을 계산하는 foo 함수를 정의한 뒤, 두 팀의 능력치 차이를 계산하여 minDiff와의 비교로 더 작은 값을 계속 갱신해준다. 모든 경우에 대해 탐색이 끝나면 minDiff를 출력하면 되겠다.

이 때 절반 수에 대한 조합이기 때문에 2번의 중복 작업을 하는 것과 동시에, 능력치 합을 계산하는 작업도 2번의 중복 작업을 한다. 때문에 계산값을 2로 나누어 반환하는 것이다. 다행히도 통과는 했지만, 이를 해결하는 풀이방법을 찾아봐야겠다.

결과

맞았습니다!!

모범답안

출처

from itertools import combinations
n = int(input())
data = [list(map(int, input().split())) for i in range(n)]
all = [i for i in range(1, n+1)]
k = list(combinations(all, n//2))
result = 1e9
for index in range(len(k)//2):
  a = 0
  b = 0
  for i in range(n//2):
    for j in range(n//2):
      a+=data[k[index][i]-1][k[index][j]-1]
      b+=data[k[-index-1][i]-1][k[-index-1][j]-1]
  result = min(result, abs(a-b))

print(result)

내 연산시간의 절반에 달하는 풀이가 있어 분석해 보려한다. 역시나 itertools의 combination 함수를 사용하였고, 함수에 대한 모든 경우를 k 배열에 저장한다. 모든 경우의 수의 절반만큼 index를 for문으로 돌려주는데, 이는 중복 작업을 배제하기 위함인 것 같고, 이렇게 하면 정확히 반대는 하지 않는다는 것을 알게 되었다.

아쉬운 점은 문제에서 제시한대로 정직하게 1부터 N까지의 팀으로 해주기 위해 인덱스를 밀어주었으며, a와 b를 더할 때 이 인덱스의 차이를 매번 계산하여 실수가 생길 수 있었다. 그리고 k의 길이는 len(k)로 하면 시간이 O(n)만큼 걸리기 때문에 조합의 특성을 이용해 계산하여 O(1)의 시간으로 계산하면 좋았을 것 같다. 그런 부분은 조금 아쉬웠다.