[BOJ/Step14] 14889 : 스타트와 링크 (Python)

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

쉽게 풀었는데 바보같은 부분 때문에 틀려서 한참 머리 싸맴....

마지막에 gap 리스트 구할때 범위 설정을 멍청하게 해서 ㅡㅜㅠ 어휴 멍청이 답답아

 

팀 리스트를 인자로 전달하면 그 팀의 능력치를 계산해서 반환하는 함수 t_status()

  1. 이중 루프 사용

    1-1. 전달된 팀 리스트의 팀원 i

    1-2. 1-1의 팀원 i와 다른 팀원 j 의 점수 Sij

    1-3. Sij를 total에 더해준다

  2. 최종 total 반환

 

1. n을 입력받고 1~n까지의 수를 저장한 p 리스트 생성

2. 능력치를 이중 리스트 status 에 저장

3. p리스트의 인원 중 n//2 만큼의 인원을 뽑을 수 있는 조합을 리스트 team 에 저장 => itertools 모듈의 combinations() 함수 사용

4. 각 팀의 능력치를 t_status() 함수로 구해 리스트 team_status 에 저장

5. 리스트 team_status의 [0]과 [n-1]의 차, [1]과 [n-2]의 차, …, [(n/2)-1], [n/2]의 차를 리스트 team_status_gap 리스트에 저장

6. team_status_gap의 최솟값을 출력 

 

=> 스타트 팀과 링크 팀을 각각 나누지 않은 이유

    team[0] 과 team[n-1] 은 짝이다. team[0] + team[n-1] 이 온전한 team이 됨

= 스타트 팀이 team[0] 조합이면 링크 팀은 반드시 team[n-1] 조합이 된다

= 두 팀의 능력치 차이의 최솟값을 구해야 하는 문제이기 때문에 team[0] 과 team[n-1] 의 차이를 구하면 된다

 

# 14889.py

import itertools


def t_status(t):
    total = 0
    for i in t:
        for j in t:
            s = status[i-1][j-1]
            total += s
    return total


n = int(input())
p = [i for i in range(1, n+1)]
status = [[i for i in map(int, input().split())] for _ in range(n)]

team = list(itertools.combinations(p, n//2))

team_status = [t_status(i) for i in team]
team_status_gap = [abs(team_status[i] - team_status[-1-i]) for i in range(len(team)//2)]

print(min(team_status_gap))