[Combination] 백준#14889: 스타트와 링크/Python 풀이

📝 문제

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

14889번: 스타트와 링크

💡 접근법

조합(Combination)을 활용하여 문제를 해결하였습니다. 총 2팀이기 때문에 하나의 팀을 구성하면 자동으로 나머지 한 팀의 팀원은 정해집니다. 먼저, 콤비네이션을 활용하여 한 팀을 구성할 수 있는 모든 경우를 구합니다. 팀 내 \(i\), \(j\)번째 구성원 간의 시너지로 짝을 이루어 능력치를 더하는 과정을 반복합니다. start 팀과 link 팀 각각의 능력치 합의 차를 절댓값으로 받는 과정을 반복하여 최솟값을 찾습니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline
from itertools import combinations

def solve():
    global answer
    # start 팀을 구성할 수 있는 모든 경우
    for start_member in list(combinations(member_all, N//2)):
        start_total = link_total = 0
        # link 팀원 = 전체 멤버에서 start 팀원 제외
        link_member = list(set(member_all) - set(start_member))
        # 팀별 능력치 시너지(S_ij + S_ji) 계산
        for i, j in list(combinations(start_member, 2)):
            start_total += s_all[i][j]
            start_total += s_all[j][i]
        for i, j in list(combinations(link_member, 2)):
            link_total += s_all[i][j]
            link_total += s_all[j][i]
        answer = min(answer, abs(start_total - link_total))

if __name__ == "__main__":
    N = int(input())
    s_all = [list(map(int, input().split())) for _ in range(N)]
    # 전체 팀원 번호
    member_all = list(range(N))
    answer = int(1e9)
    solve()
    print(answer)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline
from itertools import combinations

• sys 모듈
  • 파이썬 내장 함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.
• combinations 모듈
  • 순서를 고려하지 않고 전체 원소 중 \(N\)개 뽑는 경우의 수를 구해주는 조합(Combination)을 지원합니다.

(2) 연산 함수

def solve():
    global answer
    # start 팀을 구성할 수 있는 모든 경우
    for start_member in list(combinations(member_all, N//2)):
        start_total = link_total = 0
        # link 팀원 = 전체 멤버에서 start 팀원 제외
        link_member = list(set(member_all) - set(start_member))
        # 팀별 능력치 시너지(S_ij + S_ji) 계산
        for i, j in list(combinations(start_member, 2)):
            start_total += s_all[i][j]
            start_total += s_all[j][i]
        for i, j in list(combinations(link_member, 2)):
            link_total += s_all[i][j]
            link_total += s_all[j][i]
        answer = min(answer, abs(start_total - link_total))

하나의 팀을 구성할 수 있는 모든 경우에서 팀별 능력치의 합을 구하고, 팀 간 능력치 합의 차가 최소가 되는 값을 찾습니다.

(3) main 함수

if __name__ == "__main__":
    N = int(input())
    s_all = [list(map(int, input().split())) for _ in range(N)]
    # 전체 팀원 번호
    member_all = list(range(N))
    answer = int(1e9)
    solve()
    print(answer)

📝 채점 결과

채점 결과

채점 결과, PyPy3와 Python3 모두에서 패스했습니다. 콤비네이션 및 반복문과 같은 복잡한 연산이 있어 Python3보다 PyPy3가 더욱 빠르게 연산했네요 :)

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/etc/boj_14889.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.