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

링크

백준 14889 스타트와링크

팀을 짜기위해 조합을 만들고 조합의 요소들로 시너지테이블을 참고해서 점수를 더해주면 된다.
조합을 만들기 위해 함수를 직접 구현했다.
해당 문제의 경우 전체 만들수 있는 조합의 절반만 구하면 나머지는 전체집합에서 차집합을 만들어서 나머지 절반의 조합을 구할 수 있다.
이를 구현하기 위해 팩토리얼 함수를 구현해 나올 수 있는 조합 갯수를 구해서 절반만큼만 조합을 생성하도록 했다.
가지치기를 하고싶었으나 어떻게 해야할지 고민만하고 구현하진 못했다.
다 풀고나서야 그때그때 값들을 계산해서 더해주면서 함수의 인자로 넘겨주면 될 것 같다는 생각이 들었다. 다음에 비슷한 문제를 풀 땐 이런식으로 구현해봐야겠다.

정답 코드

def fac(n):
    ini = 1
    for i in range(1, n + 1):
        ini *= i
    return ini

def score_count(idx, j):
    global cnt, min_score

    if idx == (N // 2):
        if cnt < comb_num:
            cnt += 1
            start = sel
            link = list(set(person) - set(start))
            start_score = 0
            link_score = 0
            for i in range(N // 2):
                for j in range(N // 2):
                    start_score += arr[start[i]][start[j]]
                    link_score += arr[link[i]][link[j]]
            dif = abs(start_score - link_score)
            if dif < min_score:
                min_score = dif

    else:
        for i in range(j, N):
            if visit[i] == 0:
                visit[i] = 1
                sel[idx] = person[i]
                score_count(idx + 1, i + 1)
                visit[i] = 0

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

person = [i for i in range(N)]
visit = [0] * N
sel = [0] * (N // 2)
cnt = 0 #조합 완성 갯수
min_score = 999999999
comb_num = (fac(N) / (fac(N // 2) * 2) // 2) #nCr

score_count(0, 0)
print(min_score)

알게된 것👨‍💻

• 이 문제를 풀고나서야 파이썬이 순열, 조합에 대한 내장함수가 있는 것을 알았다..
  공부할때야 이렇게 푼다지만 코딩테스트를 위해서 내장함수를 활용해서 문제를 푸는것도 연습해야 겠다.