14889 스타트와 링크 (실버 1)

백준 14889 스타트와 링크 (실버 1)

링크: 14889 스타트와 링크

---

접근 방법

• 그래프 입력을 받고, combinations 함수로 팀 편성
• 편성된 선수는 팀 A, 안된 선수는 팀 B로 설정
• 점수 계산

---

소스 코드

소스 코드: 93249959 제출

import sys
from itertools import combinations

input = sys.stdin.readline

# N 입력
N = int(input())

# 선수 능력치 입력
graph = []
for _ in range(N):
    row = [int(i) for i in input().split()]
    graph.append(row)

# combinations 함수로 팀 편성
team_comb = list(combinations(range(N), N//2))

# 출력할 최소 차이
min_score = 2001

# 팀에 맞게 점수 계산
for teamA in team_comb[:len(team_comb) // 2]:
    teamA = set(teamA)
    scoreA = 0; scoreB = 0
    for i in range(N):
        isA = False
        if i in teamA:
            isA = True

        for j in range(i+1, N):
            if isA and j in teamA:
                scoreA += graph[i][j] + graph[j][i]
            elif not isA and j not in teamA:
                scoreB += graph[i][j] + graph[j][i]

    min_score = min(min_score, abs(scoreA - scoreB))

print(min_score)

---

코드 개선 사항(GPT 4o)

import sys
from itertools import combinations

input = sys.stdin.readline

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

players = list(range(N))
min_diff = float('inf')

for teamA in combinations(players, N // 2):
    teamB = [p for p in players if p not in teamA]

    scoreA = sum(graph[i][j] + graph[j][i] for i, j in combinations(teamA, 2))
    scoreB = sum(graph[i][j] + graph[j][i] for i, j in combinations(teamB, 2))

    min_diff = min(min_diff, abs(scoreA - scoreB))

print(min_diff)

• 리스트 입력도 한 줄로 작성
• min_socre의 기본 값을 float('inf')로 설정
• 점수를 계산하는 과정에서도 combinations를 활용

---

결론

• 나름 최적의 알고리즘을 찾은 것 같아 좋지만, GPT의 코드를 확인해보니 내가 원하는 수준의 완벽한 코드가 나왔다.
• 참고해서 더욱 공부해야할 것 같다.