[Algorithm] 삼성 SW 역량테스트 2017 하반기 오전 1번 문제 조삼모사, 코드트리 | 파이썬

※ 조삼모사

https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk/description?page=1&pageSize=20&tier=1%2C10

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제]

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 )

[출력 조건]

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

[입력 예시1]

4

0 5 9 1

3 0 5 10

4 4 0 7

1 12 6 0

[출력 예시1]

5

[입력 예시2]

6

0 100 1 1 1 1

1 0 30 30 1 1

1 1 0 1 1 1

1 1 1 0 1 1

1 1 1 1 0 1

1 1 1 1 40 0

[출력 예시2]

19

 

문제 해결 TIP

차례대로 해결해보자. 1) n개의 일을 n/2개씩 나누어 나올 수 있는 모든 조합을 저장한다. 1,2,3,4의 일이 있을 때 1,4이 아침으로 조합되었다면 남은 숫자 2,3이 저녁으로 조합되도록 모든 조합들을 아침과 저녁으로 나누어 저장한다. 2) 업무 간의 상성 그래프를 참고하여 일의 총 업무 강도를 계산한다. 계산후 answer 리스트에 저장한다. 3) answer 리스트에서 2개씩 차이를 구하고 최솟값을 출력한다.

 

전체 코드

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

#아침과 저녁으로 나뉘는 조합
k = n/2
def combination(elements, k, start, current, result):
    if len(current) == k:
        result.append(current[:])
        return
    for i in range(start, len(elements)):
        current.append(elements[i])
        combination(elements, k, i + 1, current, result)
        current.pop()
    return result
result = []
combination(range(1,n+1), k, 0, [], result)

morning = []
afternoon = []
for i in range(int(len(result)/2)):
    morning.append(result[i])
    afternoon.append(result[len(result)-i-1])
# print(morning)
# print(afternoon)

#일의 업무 강도 계산하기
a = 0
b = 0
def density(arr):
    amount = 0
    for i in range(len(arr)-1):
        for j in range(i+1,len(arr)):
            a = arr[i]
            b = arr[j]
            amount += graph[a-1][b-1] + graph[b-1][a-1]
    return amount

answer = []
for i in range(len(morning)):
    answer.append(density(morning[i]))
    answer.append(density(afternoon[i]))

#차이 구하기
count = float("inf")
for i in range(0,len(answer)-1,2):
    count = min(count, abs(answer[i]-answer[i+1]))
print(count)