오늘의 문제
https://www.acmicpc.net/problem/14889
이 문제 또한 구신의 도움을 받아 코드를 이해하는 방식으로 정리한다.
백트래킹 문제들은 나중에 다시 쭉 풀어봐야 할 것 같다..
포인트 쳌쳌
- 이중 리스트 구조를 갖도록 팀의 능력치를 입력받는다. 이 팀을 A팀이라고 가정한다.
- n명의 선수들에 대해 A팀으로 선발되면 True, 그렇지 않으면(자동으로 상대팀) False 로 표시하는 isPicked배열을 정의한다.
- A팀의 수(cnt)가 n/2, 딱 절반으로 나뉘어질 때 까지 재귀를 반복하는 함수를 작성한다.
- 팀 분배가 끝나면 해당 팀들끼리의 팀 능력치를 각각의 변수(teamA, teamB)에 합산한다.
- 팀 능력치의 차이에 대해서는
abs()로 절대값을 구해줘야 한다.
풀이 코드
n = int(input())
s = [] #능력치
isPicked = [False]*n
for i in range(n):
now = list(map(int, input().split()))
s.append(now)
result = 999
def search(cnt,idx):
global result
if idx == n:
return
if cnt == n/2:
#팀 분배가 완료된 상태
teamA, teamB = 0, 0
for i in range(n):
for j in range(n):
#현재팀 능력치
if isPicked[i] and isPicked[j]:
teamA += s[i][j]
#상대팀 능력치
if not isPicked[i] and not isPicked[j]:
teamB += s[i][j]
result = min(result, abs(teamA-teamB))
return
isPicked[idx] = True
search(cnt+1, idx+1)
isPicked[idx] = False
search(cnt, idx+1)
search(0, 0)
print(result)
채점 결과
