스타트와 링크 ( 14889 번 )

14889번: 스타트와 링크

 

---

🧠 알고리즘

• 백트래킹 (Backtracking)

 

✔️ 동작 방식

문제 핵심 아이디어: 스타트 팀과 링크 팀을 나누어 팀 점수 차이를 최소화

1. 재귀 구조
   • 재귀 함수 _bk(last_num, teams_count)를 이용해 스타트 팀의 멤버를 하나씩 선택
   • visit[i] = False이면 i번째 사람을 스타트 팀에 포함
2. 팀 구성 완료 시 점수 계산
   • 스타트 팀: visit[i]가 True인 사람들
   • 링크 팀: visit[i]가 False인 사람들
   • 점수는 모든 팀원 쌍 (i,j)의 합을 계산
   • 절대값 차이를 구해 answer 갱신
3. 조기 종료
   • 팀 점수 차이가 0이면 더 이상 볼 필요 없음 → exit()로 즉시 종료
4. 재귀 탐색
   • last_num부터 n까지 반복하면서 아직 선택되지 않은 사람을 스타트 팀에 추가
   • 재귀 호출 후 상태 복원 (visit[i] = True)
5. 최종 결과
   • 모든 조합 탐색 후 최소 점수 차이를 출력

---

 

🧾 코드

import sys

def _bk(last_num, teams_count):
    global answer
    if teams_count == n // 2:
        star, link = 0, 0

        for i in range(n):
            for j in range(n):
                if i != j:
                    if visit[i] and visit[j]: # star 팀
                        star += map_list[i][j]

                    if not visit[i] and not visit[j]: # link 팀
                        link += map_list[i][j]
        answer = min(answer, abs(star - link))

        # 조기 종료
        if answer == 0:
            print(0)
            exit()
            
        return

    for i in range(last_num, n):
        if visit[i]:
            visit[i] = False

            _bk(i + 1, teams_count + 1)

            visit[i] = True
            

n = int(sys.stdin.readline().rstrip())
map_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
visit = [True] * n
answer = float('inf')
_bk(0, 0)
print(answer)

---

 

⏱️ 시간 복잡도

_bk(last_num, teams_count) : 벡트리킹 n//2 조합을 탐색 ( 지수형 시간 복잡도 )
	# 내부 점수 계산 로직 ( 이차형 시간 복잡도 )
    for i in range(n):
		for j in range(n):
        
해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O(2 ** n) * n **2 ) )