링크 : https://www.acmicpc.net/problem/14889
14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
- 문제
- 소요시간: 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. 백트래킹으로 풀었으면 좋았을 것 같다
'알고리즘(백준) > 브루트 포스' 카테고리의 다른 글
| [알고리즘/브루트 포스] 1107번 : 리모컨 - python (0) | 2024.02.29 |
|---|---|
| [알고리즘/브루트 포스] 1182번 : 부분 수열의 합 - python (1) | 2024.01.15 |
| [알고리즘/브루트 포스] 2503번 : 숫자 야구 - python (0) | 2024.01.15 |
| [알고리즘/브루트 포스] 1018번 - python (1) | 2024.01.12 |
| [알고리즘/브루트 포스] 1436번 : 영화감독 숌 - python (0) | 2024.01.12 |