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
안녕하세요.
브라아나입니다.
정답코드.
N = int(input())
S = [list(map(int, input().split())) for i in range(N)]
tmp = [0] + [i + 1 for i in range(N)] # 1,2,3,4
ans = 999999
test_list = []
v = [0] * (N + 1)
def DFS(s, lst):
global test_list
if len(lst) == int(N / 2):
test_list.append(lst)
return
for i in range(s, N + 1):
if v[i] == 0:
v[i] = 1
DFS(i + 1, lst + [tmp[i]])
v[i] = 0
# [1] 조합 만들기 - 2/N 개 만큼
DFS(1, [])
# [2] 점수 계산하기
for i in range(int(len(test_list) / 2)):
start_ability, link_ability = 0, 0
for j in range(len(test_list[0]) - 1):
for k in range(j + 1, len(test_list[0])):
si, sj = test_list[i][j], test_list[i][k]
link = test_list[int(len(test_list)) - 1 - i]
li, lj = link[j], link[k]
si, sj, li, lj = si - 1, sj - 1, li - 1, lj - 1
start_ability += S[si][sj] + S[sj][si]
link_ability += S[li][lj] + S[lj][li]
difference = abs(start_ability - link_ability)
# print("result: ", test_list[i], difference)
if ans > difference:
ans = difference
print(ans)
풀이.
더보기
N=4 일 때,
(1, 2) , (3, 4)
(1, 3), (2, 4)
(1, 4), (2, 3)
패턴을 찾아보니까 조합을 추출하고 맨 앞자리, 뒷자리 쌍을 지어주면 되겠더라구요.
예를 들면,
N=6 일 때,
(1, 2, 3), (1, 2, 4), (1, 2, 5)..
이런 조합문제들은 "N과M" 시리즈 다 풀어야하는거 알죠 ?
그렇게 조합을 풀어서 for문에 인덱스를 하나씩 가져왔더니 6자리는 3자리의 조합을 또 구해야하더라구요
조합의 조합...그래 너 쉽지 않지 ^_^
어차피 2자리 인덱스만 뽑아내면 되니까, 2개 고정값으로 조합을 뽑아내는
for i in range(n-1):
for j in range(i+1, n):
3자리 인덱스를 뽑아야 하면 3중 포문 ***
후 힘들어쪄용~~
'Python' 카테고리의 다른 글
| 14502. 연구소 시간 단축 코드 - 백트래킹 말고, python 문제 풀이 (1) | 2024.02.14 |
|---|---|
| 파이썬 백트래킹 대표 문제 N과 M (1)~(12) 시리즈 전체 풀이 (0) | 2024.02.13 |
| 1182. 부분 수열 백준 문제풀이 python - 백트래킹 (0) | 2024.02.06 |
| [SWEA] 2072. 홀수만 더하기 (0) | 2024.01.18 |
| [Python] 백준 14503 로봇청소기 파이썬 문제 풀이 BFS (2) | 2024.01.07 |