[삼성/코테기출][Python][백준][14889] 스타트와 링크 (완전탐색/백트래킹)

🍋 문제링크

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

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 149476 KB

시간 : 1252 ms

🍓 문제풀이

파이썬으로 조합 만들기

def my_combinations(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in my_combinations(arr[i+1:], r-1):
                yield [arr[i]] + next

🍉 Code

N = int(input())
power = [list(map(int, input().split())) for _ in range(N)]
member = []
for i in range(N):
    member.append(i)

def my_combinations(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in my_combinations(arr[i+1:], r-1):
                yield [arr[i]] + next

team = []
for comb in my_combinations(member, N//2):
    tmp = 0
    for comb2 in my_combinations(comb, 2):
        tmp += power[comb2[0]][comb2[1]] + power[comb2[1]][comb2[0]]
    team.append(tmp)


answer = abs(team[0] - team[-1])
for i in range(len(team)//2):
    answer = min(answer, abs(team[i] - team[-i-1]))

print(answer)

🍒 참고

(Python) 순열, 조합, 중복순열, 중복조합 쉽게 구현하기

(Python) 순열, 조합, 중복순열, 중복조합 쉽게 구현하기