[CodingTest] 백준 #14889 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

내 풀이 - 주석

from itertools import combinations,permutations
import sys
n = int(sys.stdin.readline())
arr = []
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
#조합으로 6명이면 3명씩, 4명이면 2명씩 뽑기    
combi =list(combinations([i for i in range(1,n+1)],int(n/2)))
combi_set = []
#combi에서 마지막 원소와 첫번째 원소는 각각 (1,2), (3,4) 등의 형식이므로 
#각각 link팀, start팀의 팀원이 됨
for i in range(int(len(combi)/2)):
    combi_set.append([combi[i], combi[len(combi)-i-1]])
#각 경우 당 link 팀의 점수 합
link_score = 0
#각 경우 당 start 팀의 점수 합
start_score=0
#두 팀의 점수 차를 저장하는 배열
score_gap = []

#combi_set은 [(1,2),(3,4)]와 같은 형식이므로 item은 [(1,2),(3,4)]
for item in combi_set:
    start_score = 0
    link_score = 0
    #각 팀당 순열을 구함 ex) 위의 예시에서 start팀은 1,2가 팀원이므로
    #arr[1][2]와 arr[2][1]을 더해야 하므로 (1,2),(2,1)의 순열을 구하여 
    #arr에서 점수를 가져와 더해준다.
    start_lst=list(permutations(item[0],2))
    link_lst =list(permutations(item[1],2))
    
    for i in range(len(start_lst)):
        start_score+=arr[start_lst[i][0]-1][start_lst[i][1]-1]
        link_score+=arr[link_lst[i][0]-1][link_lst[i][1]-1]
    #두 점수 차를 절댓값으로 구하여 score_gap에 append한다.
    score_gap.append(abs(start_score-link_score))
#두 점수 차의 최솟값을 출력한다.
print(min(score_gap))

 

조합으로 팀을 나눈 후 (예시: [1, 2, 4], [3, 5, 6]) 

각 팀의 점수를 순열을 이용하여 모든 경우를 다 구하여 더해주었다. (ex, [1, 2, 4]의 경우, (1, 2}, (2, 1), (1, 4}, (4, 1}, (2, 4), (4, 2))

score_gap에 두 팀의 점수 차를 append 해주고, 최소 값을 출력하였다.

 

주석이 없는 코드는 맨 아래에서 확인할 수 있다.

---

 

다른 사람 코드 1 - 차집합 이용

from itertools import combinations as c

n = int(input())
array = [i for i in range(n)]
matrix = []
for _ in range(n):
    matrix.append((list(map(int, input().split()))))
result = int(1e9)
for r1 in c(array, n//2):
    start, link = 0, 0
    r2 = list(set(array) - set(r1))
    for r in c(r1, 2):
        start += matrix[r[0]][r[1]]
        start += matrix[r[1]][r[0]]
    for r in c(r2, 2):
        link += matrix[r[0]][r[1]]
        link += matrix[r[1]][r[0]]
    result = min(result, abs(start-link))
print(result)

 

---

다른 사람 풀이 2 - [- sth] 인덱스 사용

import sys
from itertools import combinations

N = int(sys.stdin.readline())
S = []
for i in range(N):
    S.append(list(map(int, sys.stdin.readline().split())))

all_players = [i for i in range(N)]
teams = []
for t in combinations(all_players, N // 2):
    teams.append(list(t))

answer = []
for t in range(len(teams) // 2):

    A_stats = 0
    for i in teams[t]:
        for j in teams[t]:
            A_stats += S[i][j]

    B_stats = 0
    for i in teams[-(t + 1)]:
        for j in teams[-(t + 1)]:
            B_stats += S[i][j]

    answer.append(abs(A_stats - B_stats))

print(min(answer))

 

나는 아래 코드 처럼 combi_set을 만들어, start와 link팀을 나누었는데 

for i in range(int(len(combi)/2)):
    combi_set.append([combi[i], combi[len(combi)-i-1]])

 

위 코드는 [- ~] 인덱스를 사용하여 다음과 같이 팀을 나누었다.

    B_stats = 0
    for i in teams[-(t + 1)]:
        for j in teams[-(t + 1)]:
            B_stats += S[i][j]

---

 

내 풀이 - 주석 X

from itertools import combinations,permutations
import sys
n = int(sys.stdin.readline())
arr = []
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
combi =list(combinations([i for i in range(1,n+1)],int(n/2)))
combi_set = []

for i in range(int(len(combi)/2)):
    combi_set.append([combi[i], combi[len(combi)-i-1]])

link_score = 0
start_score = 0
score_gap = []

for item in combi_set:
    start_score = 0
    link_score = 0
    
    start_lst=list(permutations(item[0],2))
    link_lst =list(permutations(item[1],2))
  
    for i in range(len(start_lst)):
        start_score+=arr[start_lst[i][0]-1][start_lst[i][1]-1]
        link_score+=arr[link_lst[i][0]-1][link_lst[i][1]-1]
        
    score_gap.append(abs(start_score-link_score))
print(min(score_gap))

---

[ 출처 ]

https://sorryhyeon.tistory.com/13

https://ye333.tistory.com/80