[백준 15661] 링크와 스타트

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

	1	2	3
4		5	6
7	1		2
3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

---

풀이

풀이 방법은 앞서 풀었던 "스타트와 링크" 문제와 동일하게 접근하였다

스타트 팀과 링크 팀에 선수를 넣어주는 과정에 재귀를 사용하였고

스타트팀에 넣어준 재귀호출 / 스타트팀에서 뺀 후 링크팀에 넣어준 재귀호출로 각 팀을 조합한 후

재귀 탈출조건으로 현재 선수의 번호를 가리키는 pointer변수가 N값을 넘어가는 경우로 걸고 진행하였다

# 재귀 부분집합 반복검사
def start_link(idx, pointer):
    if pointer >= N and (idx >= 1 or idx <= N//2):
        compare_team(start,link)
        return
    start.append(pointer)
    start_link(idx+1,pointer+1)
    start.pop()
    link.append(pointer)
    start_link(idx,pointer+1)
    link.pop()

각 팀은 한명 이상이여야하는 조건이 있기에 변수idx로 스타트팀의 선수인원을 카운트하고 idx의 범위를 1이상 N//2이하로 지정하였다. N//2를 최대로 둔 이유는 어차피 pointer번호의 선수는 링크팀 또는 스타트팀으로 들어가기에 대칭 구조를 이루게 되고 N//2를 넘어간 시점에서는 앞서 검사한 팀 능력치를 한번 더 검사하는 꼴이 되기 때문이다. 

무엇보다 계속 시간초과가 나서 시간을 줄여보고자 수정했다

 

#집합 간 능력치 비교
def compare_team(start, link):
    global compare_value     
    A_team = 0
    B_team = 0
    for i in start:
        for j in start:
            A_team += S[i][j]
    for l in link:
        for m in link:
            B_team += S[l][m]
    if compare_value == -1:
        compare_value = abs(A_team-B_team)
    if compare_value > abs(A_team-B_team):
        compare_value = abs(A_team-B_team)

그래도 시간초과가 낫고

pypy3으로 실행하니 통과했다

 

더 자세히 알아봐야겠지만 찾아본 결과 pypy3는 인터프리터 방식의 python3 성능 개선을 목적으로 만들어져 캐싱 기능이 있다고 한다. 따라서 위 풀이와 같이 재귀, 반복이 많은 코드에서 메모리 캐싱으로 python3보다 속도가 빠른 것으로 보인다. 그렇다고 pypy3만 사용하기엔 python3가 성능이 뛰어난 코드도 있다고 하니 상황에 맞게 사용해야할듯 하다.