백준 14889. 스타트와 링크

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

14889번: 스타트와 링크

 

개인적으로 굉장히 까다로웠던 문제. 한 팀이 이루어질 수 있는 모든 경우의 수를 구해서, 팀에 속한 i,j와 그렇지 못한 i,j를 분류해서 처리했더니 답은 맞게 나왔으나 시간 초과가 떴다.

 

그래서 리스트에 팀원의 인덱스를 넣는 게 아닌, 이미 고정된 크기의 배열에서 TF를 이용해 분류하는 방법을 선택해봤다.

 

그리고 TF를 이용해서 백트래킹을 하려니까 반복문에서 모든 값을 집어넣을 수 없어서, idx 변수를 따로 주고 그 다음 인덱스부터만 처리해주는 방법을 택했다.

 

[FFFFF] 길이 5의 배열에서 시작했다고 하면, 첫 싸이클에 반드시 [TFFFF]가 된다.

그 후 백트래킹을 통해 인덱스 1번째가 참인 모든 케이스 [TT???]를 찾으면 된다. 이 때 첫 번째 인덱스를 건드리면 안 되므로 한 칸 넘겨준다.

그리고 [TT???] 를 모두 찾으면 [TFT??]를 찾을 차례이므로 반복문이 증가하면서 건드려야 할 부분을 idx로 컨트롤한다.

그래서 [T????] 꼴을 모두 찾았을 때, 이제 [F????]를 찾아야 하므로 i가 넘어가면서 idx를 같이 넘겨주면 된다.

즉 i와 idx는 긴밀하게 연결되어 동작한다.

 

import math

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
start_team = [False] * n


mn = math.inf

def dfs(col, idx):
	global mn, start_team
	if col == n//2:
		pt1, pt2 = 0, 0
		for i in range(n):
			for j in range(n):
				if start_team[i] and start_team[j]:
					pt1 += arr[i][j]
				elif not start_team[i] and not start_team[j]:
					pt2 += arr[i][j]
		mn = min(mn, abs(pt1 - pt2))
		return
	for i in range(idx, n):
			start_team[idx] = True
			dfs(col + 1, i + 1)
			start_team[idx] = False

dfs(0, 0)
print(mn)