[백준 14889 스타트와 링크] 문제를 이해하기!

이 문제는 굉장히 직관적으로 생긴 코드이지만 더럽게 푼 것 같다..ㅎ..

 

해결해야하는 문제는 다음과 같다.

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

문제설명↓

 

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

	1	2	3
4		5	6
7	1		2
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. input을 받는다.

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

이와 같은 형태의 input을 받기 위하여 다음과 같이 코드를 생성하였다.

 

from sys import stdin
n = int(stdin.readline())

effect=[]
for i in range(n):
    arr = list(map(int,stdin.readline().split()))
    effect.append(arr)

 

 

2. itertools를 활용하여 n//2개의 조합 생성하기

모든팀의 index를 가진 배열 n_list를 생성하고, 스타트와 링크 팀 즉, 두 팀으로 나누기 위해 itertools를 활용하였다.

n_list = list(range(n))
combi_list = list(itertools.combinations(n_list,n//2))

 

 

3. 스타트 팀과 링크 팀의 능력치 합산의 차 중 최소값 구하기

 

예를 들어, 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

 

이 예시를 보면 S01 + S10 +( S00 + S11) =  1+4+(0+0) = S01 + S10= 5 와 같다는 것을 알 수 있다.

이러한 방법을 통해 i번째 combi_list에 있는 값들을 다 더하여 sum1에 저장하도록 하였다.

 

combi_list가 (0,1)로 있다면, 상대팀은 (2,3)이다.

상대팀의 경우의 수는 n_list를 담는 배열 temp에서 (0,1)의 값을 차례대로 빼주었다.

temp에 있는 수를 활용하여 S23 + S32 +( S22 + S33) =  2+5+(0+0) = S23 + S32 = 7 를 계산하여 sum2에 저장하였다.

 

마지막으로 sum1과 sum2의 차를 구하여 최솟값을 갱신해나갔다.

min = 1000

for i in range(len(combi_list)//2) :
    temp = list(n_list)
    sum1 = 0
    sum2 = 0

    for j in combi_list[i]:
        for k in combi_list[i]:
            sum1 += effect[j][k]

    for j in range(n//2):
        temp.remove(combi_list[i][j])

    for j in temp :
        for k in temp:
            sum2 += effect[j][k]

    if min > abs(sum1 - sum2) :
        min = abs(sum1 - sum2)

 

 

4. 최종 코드

from sys import stdin
import itertools
n = int(stdin.readline())

effect=[]
for i in range(n):
    arr = list(map(int,stdin.readline().split()))
    effect.append(arr)

n_list = list(range(n))
combi_list = list(itertools.combinations(n_list,n//2))
min = 1000


for i in range(len(combi_list)//2) :
    temp = list(n_list)
    sum1 = 0
    sum2 = 0

    for j in combi_list[i]:
        for k in combi_list[i]:
            sum1 += effect[j][k]

    for j in range(n//2):
        temp.remove(combi_list[i][j])

    for j in temp :
        for k in temp:
            sum2 += effect[j][k]

    if min > abs(sum1 - sum2) :
        min = abs(sum1 - sum2)

print(min)

 

이 문제는 코드라인 수는 짧지만 굉장히 비효율적인 것 같다.

다음부터는 시간과 메모리도 생각하며 짜는 연습을 해봐야 겠다.