[알고리즘/브루트 포스] 14889번 : 스타트와 링크 - python

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

14889번: 스타트와 링크

 

---

• 문제
• 소요시간: 55분 48초

---

• 설계하기(접근방법) 

1. 입력받기

팀원 배열을 입력받는다

 

2. 구현하기

가능한 팀원의 조합을 구해서

배열에 해당되는 값을 더한다

 

조합의 경우

모든 것을 구할 필요가 없다

 

앞이 1로 시작하는 케이스 즉

팀원이 2명이라면

1,2

1,3

1,4 만 구해도

 

3,4

2,4

2,3 이 따라온다

 

둘 중 한개의 배열에는 1이란 선수가 들어가야 한다

그리고 두 개의 배열은 숫자가 같다

 

따라서 1이 들어간 배열은 전체 배열의 반인 것이 보장된다

 

그 후 각각의 케이스의 차를 구해서

 

가장 차이가 적게 나는 케이스를 출력한다

 

3. 출력하기

최소 케이스를 출력하낟

 

 

---

• 코드(출력)

from itertools import combinations, permutations

n = int(input())
power_list = [list(map(int, input().split())) for _ in range(n)]

# 각 팀원
team_person = n // 2
# 선수 번호 0 ~ n -1
player = [i for i in range(n)]
# 선수 번호는 0번부터 시작
team = list(combinations(range(1,n), team_person - 1))

# 팀 1
start_team = [[0] for _ in range(len(team))]
# 팀 2
link_team = []

for i in range(len(start_team)):
    start_team[i] = [0] + list(team[i])

# 팀 1, 팀 2 케이스 구하기

for i in start_team:
    temp = []
    for j in player:
        if j not in i:
            temp.append(j)
    link_team.append(temp)
            
start_team_power = []
link_team_power = []

# 각각 힘의 합 구하기

for i in start_team:
    power = 0
    temp = list(permutations(i, 2))
    for j in temp :
        x, y = j
        power += power_list[x][y]
    start_team_power.append(power)

for i in link_team:
    power = 0
    temp = list(permutations(i ,2))
    for j in temp :
        x, y = j
        power += power_list[x][y]
    link_team_power.append(power)

## 힘 차이 구하기
power_difference = []

for i in range(len(start_team_power)):
    power_difference.append(abs(start_team_power[i] - link_team_power[i]))

## 최소값 출력
print(min(power_difference))

---

• 얻어갈 부분

1. 백트래킹으로 풀었으면 좋았을 것 같다