[BaekJoon] 백준 14889 스타트와 링크 (Python / 파이썬)

BaekJoon BOJ 백준 14889 스타트와 링크 문제는 축구를 하기 위해 모인 사람은 총 N명이고 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 스타트 팀의 능력치와 링크 팀의 능력치의 차이의 최솟값을 구하는 문제이다. 난이도는 Silver 3이다.

 

BaekJoon 14889 스타트와 링크 문제 정보

출처

- https://www.acmicpc.net/problem/14889

알고리즘 분류

- 브루트 포스 알고리즘 (brute force algorithm), 백트래킹(BackTracking)

난이도

- 실버 3 / Silver 3

 

스타트와 링크 문제 요약

• 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
• 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
• N(4 ≤ N ≤ 20, N은 짝수), Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
• 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 할 때, 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

문제 풀이 과정

1. 조합을 구하기 위해 itertools의 combinations를 import 한다.
2. 경기 인원 수와 능력치를 입력받는다.
3. N명 중 N//2명씩 두 팀으로 나누는 조합을 뽑는다.
4. 팀 조합의 개수를 저장한다.
5. 팀의 능력치 차이의 최솟값을 무한대로 정의해놓는다.
6. 팀 조합의 1번째 값 vs 마지막 값, 2번째 값 vs 마지막-1번째 값... 규칙으로 총 (팀 조합의 개수 // 2) 개의 팀 조합끼리 대결하는 경우가 있다.
7. 각 팀의 멤버들끼리에서 또 한 번 조합을 구하여 두 멤버가 만났을 때 팀에 더해지는 능력치를 팀의 능력치에 더한다.
8. 각 팀 조합마다 팀의 능력치의 차이를 구하고 모든 팀의 조합 중 가장 최소의 차이가 나는 팀의 능력치 차이를 구하여 출력한다.

 

코드 및 설명

• ability - 각 선수들이 같은 팀에 속했을 때 팀에 더해지는 능력치를 저장한 리스트
• combination - 나눌 수 있는 팀의 조합
• combLen (// 2) - 나눌 수 있는 팀 조합의 개수
• ans - 팀의 능력치의 차이의 최솟값
• startComb, linkComb - 각 팀 내에서 두 멤버들의 조합
• startTeam, linkTeam - 각 팀의 능력치
• diff - 스타트 팀과 링크 팀의 능력치의 차이

from itertools import combinations as c

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

# 나눌 수 있는 팀의 조합
combination = list(c(list(range(N)), N // 2))
combLen = len(combination)  # 팀 조합의 개수

ans = float("inf")
# 팀 나누기
for team in range(combLen // 2):
    # 각 팀의 멤버들 조합
    startComb = list(c(combination[team], 2))
    linkComb = list(c(combination[combLen - team - 1], 2))

    # 각 팀의 능력치
    statTeam = linkTeam = 0
    for player in startComb:
        statTeam += ability[player[0]][player[1]] + ability[player[1]][player[0]]

    for player in linkComb:
        linkTeam += ability[player[0]][player[1]] + ability[player[1]][player[0]]

    diff = abs(statTeam - linkTeam)  # 각 팀의 능력치 차이
    ans = min(ans, diff)  # 팀의 능력치의 최소 차이

print(ans)

---

삼성 코딩 테스트는 라이브러리를 못쓰게 한다는데, combinations를 안 쓰고는 DFS 알고리즘을 사용하여 풀 수 있는데, DFS를 더 깊이 공부하면 다시 풀어봐야겠다. 갈 길이 멀다..

 

BaekJoon 백준 BOJ 14889 스타트와 링크 문제를 파이썬 python으로 풀어보았다. 난이도는 Silver 실버 3이다.