[모의 SW 역량테스트] 요리사

SWEA 문제 모음: https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

문제를 잘못 이해해서 한참 빙빙 돌다가 정답에 접근한 문제. 문제 설명이 뭔가... 애매하거나 부족한 것 같은데 다시 읽어보니 내가 잘못 읽은 것 같기도 하고... 댓글에도 있던 것 같은데 N이 조금 더 큰(6, 8) 예시가 있었다면 쉽게 이해했을 것 같다.

 

음식은 2개 만드는 상황이고, N이 무조건 짝수니 각 음식에 식재료가 N//2개 들어가게 된다. 식재료 간 시너지는 가능한 모든 시너지를 다 더해야 한다.(함수 cal)

 

최대 N이 16이니 가능한 모든 식재료를 선택하는 경우의 수(N//2개 선택)를 dfs로 구하고, 시너지 총합이 가장 큰 경우를 출력하면 된다.

 

	t = int(input())
	def cal(lst): # 식재료 시너지 계산
	taste = 0
	for i in range(n//2): # 가능한 모든 pair에 대해 S_ij 합
	for j in range(i+1, n//2):
	taste += recipe[lst[i]][lst[j]] + recipe[lst[j]][lst[i]]
	return taste
	def dfs(num ,k):
	global sol
	if num == n//2: # 각 음식 당 n//2개 식재료 사용
	A, B = [], []
	for i in range(n):
	if visited[i]: A.append(i)
	else: B.append(i)
	A_sol, B_sol = cal(A), cal(B)
	sol = min(sol, abs(A_sol-B_sol))
	return
	for i in range(k, n): # 아직 방문하지 않은 n-k개 중 선택
	if not visited[i]:
	visited[i] = True
	dfs(num+1, i+1) # num+1개 고른 상황, 식재료[i+1:-1] 중 나머지 선택
	visited[i] = False # 해당 식재료를 선택하는 모든 경우의 수 보고 난 이후 제거
	for t_idx in range(1, t+1):
	n = int(input())
	recipe = [list(map(int, input().split())) for _ in range(n)]
	visited = [False]*n
	sol = 20000*65
	dfs(0,0) # 아무것도 선택하지 않은 상황에서, n-0개 선택하는 초기 상황
	print("#{} {}".format(t_idx, sol))

view raw 요리사.py hosted with ❤ by GitHub