[Python] 백준 14889번 : 스타트와 링크 (S3)

#문제

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

#풀이 & 학습한 내용

pypy3는 python3에 비해 빠르지만 메모리를 많이 소요합니다. 이번 코드의 경우에는 시간초과가 우려되었지만, PyPy3와 Python3 모두 통과되었습니다. 또한, itertools의 combinations를 통해서 문제를 편하게 해결할 수 있었습니다. 리스트끼리 덧셈은 되지만, 뺄셈은 되지 않아서 [x for x in list(range(N)) if x not in team1]와 같이 적어 뺄셈을 구현했습니다. 또한, 2차원 배열을 입력받을 때 [list(map(int, input().split())) for _ in range(N)] 로 간결하게 입력받았습니다.

 

#소스코드

from itertools import combinations

N=int(input())
stats=[list(map(int, input().split())) for _ in range(N)] #능력치 입력받기
#print(stats)

people_comb = list(combinations(list(range(N)),N//2)) #한 팀의 조합
#print(people_comb)

ans = 9999999999

for team1 in people_comb:
  team1=list(team1) #팀1의 팀원들
  team2=[x for x in list(range(N)) if x not in team1] #팀2의 팀원들
  team1_score=0
  team2_score=0
  for players in list(combinations(team1,2)): #팀1의 팀원 2명
    team1_score+=stats[players[0]][players[1]]
    team1_score+=stats[players[1]][players[0]]
  for players in list(combinations(team2,2)): #팀2의 팀원 2명
    team2_score+=stats[players[0]][players[1]]
    team2_score+=stats[players[1]][players[0]]
  if ans > abs(team1_score-team2_score):
    ans = abs(team1_score-team2_score)

print(ans)

 

github.com/HoYoungChun/Algorithm_PS/blob/master/Backtracking/BOJ_14889.py

HoYoungChun/Algorithm_PS