[CT] 조삼모사

1. 문제

• n개의 일 → 아침/저녁으로 n/2씩 처리

• 업무 강도 / 업무 간 상성 Pij

  • ex)

    

    • 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로 최솟값

⇒ 아침의 하는 일의 업무 강도와 저녁에 하는 일의 업무 강도의 차이의 최솟값?

2. 풀이

1. 구현… →
   • 아침/저녁에 작업할 일의 조합을 구해서 각각에 대한 업무 강도를 모두 계산
   • 조합을 구하고 정렬을 할 경우, i번째 원소가 아침에 작업할 일이라면 -i-1번째 원소가 저녁에 작업할 일이다
     • ex) [1,2,3,4] 에서 일의 조합을 구한다면
       • [ [1,2] , [1,3], [1,4][2,3], [2,4], [3,4] ] 이므로
       • 아침 저녁의 조합은 [1,2] + [3,4], [1,3] + [2,4], [1,4] + [2,3] 일 것이다
   • 너무나도 당연히 시간복잡도가 엄청나다
2. DFS / 백트래킹
   • 조합을 다 구하고 일의 강도를 계산하는 것이 아니라, 조합을 구하면서 강도를 계산하고, 업무 강도 차이의 최솟값을 구한다!
     • 1부터 n까지의 업무들에 대한 배열의 index를 이용해서
     • 업무 강도를 구하는 함수에서 depth 변수를 이용하여 아침 업무가 n//2개 될 때만 저녁의 업무를 조건문으로 구하고 각각의 업무의 강도를 계산한다
     • 아침/저녁 업무 조합에 대한 업무의 강도 차이를 현재의 최솟값 ans와 비교하여 최종적으로 가장 작은 값을 최종적으로 반환한다

3. 코드

1. 조합 구현

   def combinations(arr, r):
       for i in range(len(arr)):
           if r == 1:
               yield [arr[i]]
           else:
               for next in combinations(arr[i+1:], r-1):
                   yield [arr[i]] + next
               
   def solution():
       n = int(input())
       half = n//2
   
       work = [ list(map(int, input().split())) for _ in range(n) ]
   
       task = [i for i in range(n)]
       combo = sorted(list(combinations(task, half)))
       
       balance = []
       
       for jobs in combo:
           intensity = 0
           intensities = list(combinations(jobs, 2))
           
           for i, j in intensities:
               intensity += work[i][j]
               intensity += work[j][i]
               
           balance.append(intensity)
           
       min_diff = abs(balance[0] - balance[-1])
       
       for i in range(1, len(balance)//2):
           diff = abs(balance[i] - balance[-i-1])
           if min_diff > diff : 
               min_diff = diff
           
   
       print(min_diff)
   
   solution()

1. DP/백트래킹

   # 일의 양 (2의 배수)
   n = int(input())
   
   # 업무 간의 상성 Pij
   work = [list(map(int, input().split())) for _ in range(n)]
   
   def work_intensity(day):
       res = 0
       for i in range(n//2):
           for j in range(i+1, n//2):
               res += work[day[i]][day[j]]
               res += work[day[j]][day[i]]
       return res
   
   def dfs(idx, depth):
       global ans
       if depth == n//2:
           temp2 = [i for i in range(n) if i not in temp]
           ans = min(ans, abs(work_intensity(temp) - work_intensity(temp2)))
           
       for i in range(idx + 1, n): #idx = 0 부터 시작하면 
           temp.append(i)
           dfs(i, depth+1)
           temp.pop()
   
   total = set(range(n))
   temp = [0]
   ans = float("INT")
   dfs(0,1)
   
   print(ans)

+α

• 동일 문제 : 백준 14889 스타트와 링크

• 참고

  • https://developer-ellen.tistory.com/50