[백준 python] 14889번 스타트와 링크

문제 링크

14889번: 스타트와 링크

문제 설명

• 짝수 N명의 사람들을 두개의 팀으로 나누어 각 팀의 능력치를 계산해 비교해 차이가 최소인 팀 구성을 구하는 문제
• 팀이 구성되면 구성원 끼리 순서가 없기 때문에 조합을 찾는 문제로 생각해 풀 수 있음

고민한 부분

• python의 내장 라이브러리인 itertools의 combinations함수를 사용할 수 있을지 확인해보고 싶었다
• 백트래킹 문제가 조금 까다롭게 나오는 경우 중간에 탐색할 필요 없는 조건을 찾아 가지치기를 해주어야 하는데 이 문제에서는 가지치기 할 필요 없이 조합을 구하면 되는 문제였기 때문에 내장 함수를 사용해 풀이해도 통과가 됐다
• 아래 재귀 형태로 조합을 구하는 코드와 내장 함수를 사용하는 코드를 모두 첨부했다

재귀로 조합 구하기

	import sys, math
	from itertools import permutations
	def cal_performance$team : list$:
	performance = 0
	for i in team:
	for j in team:
	if i == j:
	continue
	performance += TABLE[i][j]
	return performance
	def compare_perform$A : list, B : list$:
	"""스타트 팀과 링크 팀의 능력치 차이 계산
	Args:
	A $list$: 스타트 팀원 리스트
	B $list$: 링크팀 팀원 리스트
	Return:
	differ $int$: 능력치 차이
	"""
	return abs$cal_performance(A$- cal_performance$B$)
	def DFS$team_A: list$:
	global min_
	if len$team_A$ == N//2:
	# 차이 값 계산 & 최소값 업데이트
	team_B = [p for p in people if p not in team_A]
	min_ = min$min_, compare_perform(team_A, team_B$)
	return
	## 두번 계산되는 문제
	### ex) A = [1,2], b = [0,3] // A = [0,3], B = [1,2]는 같은 상황
	for i in range$team_A[-1], N$:
	if i in team_A:
	continue
	team_A.append$i$
	DFS$team_A$
	team_A.pop
	if __name__ == '__main__':
	turn_in = 1
	if turn_in ==0:
	sys.stdio = open$'test_case.txt'$
	N = int$sys.stdio.readline($)
	TABLE = [list$map(int, sys.stdio.readline($.split)) for _ in range$N$]
	else:
	N = int$sys.stdin.readline($)
	TABLE = [list$map(int, sys.stdin.readline($.split)) for _ in range$N$]
	people = list$range(N$)
	min_ = math.inf
	for i in range$N//2$:
	DFS$[i]$
	print$min_$

view raw boj_14889_recursion.py hosted with ❤ by GitHub

python 내장 함수 combinations 사용해 조합 구하기

	import sys, math
	from itertools import combinations
	def cal_performance$team : list$:
	performance = 0
	for i in team:
	for j in team:
	if i == j:
	continue
	performance += TABLE[i][j]
	return performance
	def compare_perform$A : list, B : list$:
	"""스타트 팀과 링크 팀의 능력치 차이 계산
	Args:
	A $list$: 스타트 팀원 리스트
	B $list$: 링크팀 팀원 리스트
	Return:
	differ $int$: 능력치 차이
	"""
	return abs$cal_performance(A$- cal_performance$B$)
	def solve:
	"""팀나누기 + 차이 최소값 구하는 main 함수
	Returns:
	_type_: _description_
	"""
	min_ = math.inf
	#팀 나누기
	A_teams = combinations$people, N//2$ # A팀 조합 리스트, B팀은 for문 안에서 새로
	for A_team in A_teams:
	B_team = [p for p in people if p not in A_team]
	diff = compare_perform$A_team, B_team$
	min_ = min$diff, min_$
	return min_
	if __name__ == '__main__':
	turn_in = 1
	if turn_in ==0:
	sys.stdio = open$'test_case.txt'$
	N = int$sys.stdio.readline($)
	TABLE = [list$map(int, sys.stdio.readline($.split)) for _ in range$N$]
	else:
	N = int$sys.stdin.readline($)
	TABLE = [list$map(int, sys.stdin.readline($.split)) for _ in range$N$]
	people = list$range(N$)
	print$solve($)

view raw boj_14889_itertools.py hosted with ❤ by GitHub