[Python/Codetree] 조삼모사

문제

n개의 일이 주어질 때 이를 아침과 저녁으로 2n​개씩 나누어처리하고자 합니다.

일마다 특성이 다르기 때문에 같이할 때의 업무 강도를 나타내는 업무 간의 상성 Pij​가 존재합니다. 예를 들어 업무 상성이 다음과 같이 주어질 때,

1, 2번 일을 아침에 3, 4번일을 저녁에 한다면

아침에 하는 일의 총 업무 강도는 P12​ + P21​ = 8이 되고

저녁의 경우 P34​ + P43​ = 13이 됩니다.

만약 1,4번 일을 아침에 2, 3번 일을 저녁에 한다면,

아침의 경우 P14​ + P41​ = 2

저녁의 경우 P23​ + P32​ = 9가 됩니다.

아침과 저녁의 일의 힘든 정도가 너무 차이가 나면 일하기가 싫어지기 때문에, 아침의 하는 일의 업무 강도와 저녁에 하는 일의 업무 강도의 차이의 최솟값을 구하고자 합니다.

위의 예시의 경우 1,2번 일과 3, 4번의 일로 나누어서 하는 것이 힘듦의 합의 차이가 5로 최솟값이 됩니다.

6개의 일이 주어질 때 아침에 2, 3, 4번일, 저녁에 1, 5, 6번 일을 한다고 했을 때,

아침의 경우 P23​ + P32​ + P34​ + P43​ + P24​ + P42​ = 64,

저녁의 경우 P15​ + P51​ + P56​ + P65​ + P16​ + P61​ = 45가 됩니다.

아침과 저녁의 업무 강도의 차이의 최솟값을 구하는 프로그램을 작성하세요.

입력 형식

첫째 줄에 일의 양 n이 주어집니다.

두번째줄부터 (n+1)번째 줄까지는 업무 간의 상성 Pij​이 주어집니다.

• 4 ≤ n ≤ 20
• n은 2의 배수이다.
• Pij​ = 0 (i = j)
• 1 ≤ Pij​ ≤ 100 ( i ≠ j )

출력 형식

아침에 하는 일과 저녁에 하는 일의 업무 강도 차이의 최솟값을 출력하세요.

풀이

Code

import sys
input = sys.stdin.readline

ans = float('INF')
def solution(n, works) :
    # 1. 백트래킹 함수 정의
    def backtracking(idx, cnt) :
        # 1-1. 종료 조건 설정
        if cnt == n // 2 :
            # 최솟값 업데이트 함수 실행
            update(morning)
            return
        # 1-2.
        for i in range(idx+1, n) :
            # 아침 일 추가
            morning.append(i)
            # 백트래킹 실행
            backtracking(i, cnt+1)
            # 아침 일 제거
            morning.pop()

    # 2. 최솟값 업데이트 함수 정의
    def update(morning) :
        global ans
        # 2-1. 저녁 업무 구하기
        evening = [i for i in range(n) if i not in morning]
        # 2-2. 일의 정도 구하기
        morning_work = evening_work = 0
        for i in range(n // 2) :
            for j in range(i + 1, n // 2) :
                morning_work += works[morning[i]][morning[j]] + works[morning[j]][morning[i]]
                evening_work += works[evening[i]][evening[j]] + works[evening[j]][evening[i]]
        ans = min(ans, abs(morning_work - evening_work))

    # 3. 아침 업무 리스트 생성
    morning = []
    # 4. 백트래킹 함수 실행
    backtracking(0, 0)
    # 5. 결과 출력
    print(ans)

if __name__ == '__main__' :
    n = int(input())
    works = [list(map(int, input().split())) for _ in range(n)]
    solution(n, works)