BOJ #14889 스타트와 링크 python

💡Github URL

: https://github.com/hansun-hub/2025-algorithm-study/blob/main/2주차/BOJ 14889.py

 

💡문제에서 구해야 할 것

문제 조건 :

• N명을 두개의 팀으로 나누는 모든 경우 탐색 후 두 팀의 능력치 최소값 찾아라

 

💡알고리즘 설계

• 백트래킹 이용해서 N/2 되는 경우 팀 구성
• 능력치 계산 _ S[i][j] + S[j][i]
• 최솟값 갱신 시켜줌

 

💡코드

import sys

def calculate_score(team, S):
    """ 주어진 팀의 능력치 합을 계산하는 함수 """
    score = 0
    for i in range(len(team)):
        for j in range(i + 1, len(team)):
            score += S[team[i]][team[j]] + S[team[j]][team[i]]
    return score

def backtrack(idx, start_team, N, S, min_diff):
    """ 백트래킹을 이용해 팀을 나누고 최솟값을 갱신하는 함수 """
    if len(start_team) == N // 2:
        link_team = [i for i in range(N) if i not in start_team]  #스타트 팀에 속하지 않은 사람들을 모아 링크 팀 만듬

        start_score = calculate_score(start_team, S)
        link_score = calculate_score(link_team, S)

        return min(min_diff, abs(start_score - link_score))

    for i in range(idx, N):
        start_team.append(i)
        min_diff = backtrack(i + 1, start_team, N, S, min_diff)
        start_team.pop()  # 백트래킹

    return min_diff

def solve():
    """ 입력을 받아서 최소 능력치 차이를 계산하는 메인 함수 """
    N = int(input())
    S = [tuple(map(int, input().split())) for _ in range(N)]

    # 최솟값 초기화
    min_diff = float('inf')

    # 백트래킹 시작
    min_diff = backtrack(0, [], N, S, min_diff)

    print(min_diff)

 

💡시간복잡도

• 백트래킹 통해서 팀을 나눌 때 _ n명 중 n/2 명을 선택하는 조합
• → O(2의 n승) (백트래킹으로 팀을 나누는 경우의 수 )

 

💡 다른 풀이 or 기억할정보

• 최솟값 초기화하는 법

 # 최솟값 초기화
    min_diff = float('inf')

• 능력치 합 구하는 법

score += S[team[i]][team[j]] + S[team[j]][team[i]]

• 백트래킹 사용법

 for i in range(idx, N):
        start_team.append(i)
        min_diff = backtrack(i + 1, start_team, N, S, min_diff)
        start_team.pop()  # 백트래킹