[백준, 삼성 기출] 14889_스타트와 링크 (Python)

14889_스타트와 링크 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (silver 2)
• 링크 : 14889번: 스타트와 링크

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 팀원을 이룰 수 있는 모든 경우의 수를 구해야한다.
>> 그리고 표에 주어진 능력치를 적용시켜 팀별로 그 합을 구하고 합의 차이가 가장 작은 경우를 찾는다.
>> 조합의 수를 구해야 함. 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from itertools import combinations

n = int(input())
nums = list(i for i in range(n))
graph = list(list(map(int,input().split())) for _ in range(n))

combis = list(combinations(nums, n//2))

min = 10000000
answer_list = []
for comb in combis:
    start = set(comb)
    link = set(nums) - start

    start = list(start)
    link = list(link)

    start_comb = list(combinations(start, 2))
    link_comb = list(combinations(link, 2))

    # print(f"start 입니다. {start}")
    # print(f"link 입니다. {link}")

    case1 = 0
    case2 = 0

    for x1, y1 in start_comb:
        case1 += graph[x1][y1] + graph[y1][x1]

    for x2, y2 in link_comb:
        case2 += graph[x2][y2] + graph[y2][x2]

    if min > abs(case1 - case2):
        min = abs(case1 - case2)
        # print(f"case1 입니다. {case1}")
        # print(f"case2 입니다. {case2}")

print(min)

(4) 정리

튜플 형태의 comb에 반대되는 조합을 어떻게 구해야하나 모르겠어서 이 부분만 찾아봤습니다.
comb를 set형태로 바꾸고 전체 숫자 set(nums)에서 해당 set(comb)를 빼면 나머지숫자로 조합된 comb를 구할 수 있었습니다.

(5) 참고

참고 풀이