swea4021.요리사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH 

SW Expert Academy

#요리사

T = int(input())
for tc in range(1,T+1):
    N= int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    answer = 999999999
    #DFS로 풀어야할 듯..
    #요리 2개니까 재료 나눌것. -같은 식재료 수일때 수를 비교 해야함!
    #level==N
    #DFS 요리A,요리B 나눠서 재귀 (식재료 인덱스를 나누는 과정(?))

    def cook(level,Acook,Bcook):
        global answer
        if level==N: #식재료 수만큼 level이 되면 return!
            if len(Acook) == len(Bcook): #식재료는 짝수로 반반이니까 같을때!
                A,B=0,0
                for i in range(N//2):
                    for j in range(N//2):
                        A+=arr[Acook[i]][Acook[j]]
                        B+=arr[Bcook[j]][Bcook[i]]
                if answer>abs(A-B):
                    answer = abs(A-B)
            return

        cook(level+1,Acook+[level],Bcook) #A요리에 들어갈 식재료 번호
        cook(level+1,Acook,Bcook+[level]) #B요리에 들어갈 식재료 번호

    cook(0,[],[]) #level,A요리,B요리
    print(f'#{tc} {answer}')

풀이 과정

전에 DFS를 공부했을 때 2가지 가지로 나뉘는 방법을 응용함.

1. A요리에 들어갈 식재료의 인덱스와 B요리에 들어갈 식재의 인덱스를 담아 줄 리스트를 매개변수로 지정해 DFS돌리기

2. 종료 조건은 식재료의 수 일때!

3. 문제에서 짝수의 식재료를 제공하고 요리에는 절반씩 들어간다고 조건이 주어졌으므로 if문에 조건을 달아줄것

4. for문을 돌려서 각 요리별로 식재료 값 더해주고 

5. abs로 차이 구해서 최소값을 답으로 갱신