백준 14889번 - 스타트와 링크 (삼성 SW역량 테스트 기출 문제 2)

팀을 나눠서 각 선수들의 케미(상호간의 능력치)를 구하는 문제다. 문제를 읽어보니 일단 N명의 선수를 받은 뒤 반으로 나누어서 팀을 구하고 각 팀 인원들의 케미를 구하면 되겠구나 싶었다. 팀을 나눌 때는 팀 하나가 정해지면 다른 팀은 바로 결정이 되기 때문에 두 팀을 따로 구할 필요가 없다. 팀을 나누려면 N과 M(1)문제에서 사용한 방법을 응용하면 된다.

백준 15649번 - N과 M(1)

만약 N = 4라고 생각해 보면, A팀은 (0,1), (0,2), (0,3) 의 세 종류의 팀으로 구성이 가능하다. 원래 4명 중 2명을 고르는 4C2=6(조합)의 경우의 수가 나오지만 A팀이 (0,1) B팀이 (2,3)인 경우와 A팀이 (2,3) B팀이 (0,1)인 경우는 각 팀 케미의 차를 구하는 데 동일하기 때문에 무시해줘도 된다. 즉, A[0]이 0일때만 구해주면 된다. 그리고 구할 때는 각 팀 내의 선수의 중복이 없어야하고, 오름차순이어야 한다. 팀을 모두 구하고 나면, 각 선수들을 두명씩 나누어서 케미를 구해주면 되기 때문에, 같은 방식으로 코드를 짜주면 된다.

 

##함수 선언 부분##
def Team(index):
    global sumA, sumB, min
    if index == N//2:
        B = [] #지역변수 B배열 선언
        for i in range(N): #구한 A팀을 이용해서 B팀을 구해준다.
            if i in A:
                continue
            else:
                B.append(i)
        A_chemistry(A) #A팀의 능력치를 구한다.
        B_chemistry(B) #B팀의 능력치를 구한다.
        if sumA > sumB: #gap이 음수가 나오지 않게 조건을 만들어준다.
            gap = sumA - sumB
        else:
            gap = sumB - sumA
        if min > gap: #능력치의 최솟값을 갱신해준다.
            min = gap
        sumA = 0 #초기화
        sumB = 0
        del(B) #B 삭제
    else:
        for i in range(N):
            if i in A: #중복되면 무시
                continue
            if index >= 1: #만약 A[0]이 존재하면
                if A[0] > 0: #A[0]이 0인 경우만 탐색을 할 것이기 때문에 0보다 크면 무시
                    continue
                if i < A[index-1]: #오름차순인 경우에만 탐색을 하기위한 조건
                    continue
            A.append(i)
            Team(index+1)
            A.pop()


def A_chemistry(A): 
    global sumA
    if len(A_chemi) == 2: #선수 두명의 값이 모두 들어오면 
        sumA += data[A_chemi[0]][A_chemi[1]] #각 선수끼리의 케미를 더해주고
        return sumA #반환
    else:
        for i in A:
            if i in A_chemi: #중복되면 무시
                continue
            A_chemi.append(i)
            A_chemistry(A)
            A_chemi.pop()


def B_chemistry(B): #A와 동일
    global sumB
    if len(B_chemi) == 2:
        sumB += data[B_chemi[0]][B_chemi[1]]
        return sumB
    else:
        for i in B:
            if i in B_chemi:
                continue
            B_chemi.append(i)
            B_chemistry(B)
            B_chemi.pop()
##변수 선언 부분##
data = []
N = 0
A = []
A_chemi = []
B_chemi = []
sumA = 0
sumB = 0
min = 1000000
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    data = [[int(x) for x in input().split()]for _ in range(N)]
    members = [int(x) for x in range(N)]
    Team(0)
    print(min)

처음에 문제를 봤을 때는 복잡하다고 생각했지만, 어떤 식으로 풀 지를 결정하고 차례대로 코드를 짜니까 쉽게 풀렸던 것 같다. A[0] = 0인 경우와 오름차순인 경우만 구할 때만 조금 애를 먹었다. 구글에 검색하면 나오는 다른 코드들에 비해 조금 길지만, 그 만큼 쉽게 풀어쓴 코드라고 생각한다.