[백준] 14889 스타트와 링크 (Python 파이썬)

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

14889번: 스타트와 링크

문제 설명

문제에서 n이 주어지고 1부터 n까지 차례대로 번호가 붙은 사람 n명이 존재한다.

이 n명의 사람을 두 팀으로 나눈 후 각 팀의 시너지의 합을 구하게 되는데

시너지는 문제에서 입력으로 주어진다.

n x n 형식의 배열로 주어지며 배열[1][2] 는 1과 2가 한팀일 때의 시너지를 나타낸다.

 

이 때, 두 팀의 시너지의 합의 최소값을 구하는 문제이다.

---

풀이 과정

이 문제는 두 팀의 시너지 차이의 최소값을 구해야 하므로 모든 시너지를 탐색해야 하는 브루트포스 문제이다.

 

따라서 다음과 같이 접근하였다.

① 조합(Combinations)을 이용해 모든 경우의 수(팀)를 구한다.

    n = 6 이면 6개 중에서 순서를 고려하지 않고 3개를 뽑는 경우의 수와 같다.

    그러면 팀 1 : [1, 2, 3] / 팀 2: [4, 5, 6] 등과 같이 팀을 구할 수 있다.

 

② 각 경우의 수에 대해 팀의 시너지를 구한다.

    위의 예시에서는, 팀1의 경우에는 graph[1][2] + graph[1][3] + graph[2][1] ... + graph[3][2] 를 구하고

    팀2의 경우에는 graph[4][5] + graph[4][6] + ... graph[6][5] 를 구하면 된다.

 

③ 두 팀의 시너지의 차이와 현재 최소값과 비교해

    현재 차이가 더 작다면 최소값을 현재 차이로 교체한다.

 

이를 파이썬 코드로 나타내면 다음과 같다.

from itertools import combinations

n = int(input())
graph = []
number = [i for i in range(n)]

minR = int(1e9)

for i in range(n):
    graph.append(list(map(int, input().split())))


for c in combinations(number, n//2):
    visited = [False] * n
    team1 = []
    team2 = []
    for i in c:
        visited[i] = True
        team1.append(i)

    for i in range(n):
        if not visited[i]:
            team2.append(i)

    sum1 = 0
    sum2 = 0
    for i in range(n//2):
        for j in range(n//2):
            if graph[team1[i]][team1[j]] != 0:
                sum1 += graph[team1[i]][team1[j]]
            if graph[team2[i]][team2[j]] != 0:
                sum2 += graph[team2[i]][team2[j]]

    if abs(sum1-sum2) < minR:
        minR = abs(sum1-sum2)

print(minR)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !