백준 14889번 스타트와 링크 삼성 SW역량테스트 (Python)

python백준 14889 문제 바로가기

문제 이해

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

스타트 팀: S12 + S21 = 1 + 4 = 5
링크 팀: S34 + S43 = 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

스타트 팀: S13 + S31 = 2 + 7 = 9
링크 팀: S24 + S42 = 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

사람이 6명일 때는 예를 들어 (1, 2, 3) (4, 5, 6)으로 나뉘고 이때는 표에서 (1,2)(1,3)(2,3)(2,1)(3,1)(3,2)에 해당하는 값을 다 더한것이 팀의 능력치이다.

문제 접근

문제를 보고 나는 3가지의 상황으로 나누었다.

• 나올 수 있는 팀의 조합을 담고있는 리스트를 생성하기
• 그렇게 해서 나온 팀의 능력치의 합을 구하기
• 능력치의 차가 가장 작을 때의 능력치 차이를 구하기

우선 나올 수 있는 팀의 조합을 담고있는 리스트를 생성하는 방법은 조합을 사용해야겠다고 생각했다.

조합이란 예를 들어 6개의 번호가 써져있는 공들에서 3개를 뽑으려고 할때 가능한 경우의 수를 말한다.

따라서 지금과 상황이 굉장히 비슷하다. 우리는 N명에서 N/2만큼의 인원을 뽑아 start팀에 넣어야 한다.
이 때 가능한 경우의 수를 담는 리스트를 이 조합을 사용하여 생성한다.
조합은 import itertools를 사용하고 그 중에서 combination을 사용한다.

이렇게 조합으로 구한 리스트들의 능력치의 합을 다른 리스트에 저장하도록 했다.

그 후에 능력치의 차이를 구하고 가장 작은 수를 저장하고 출력하도록 했다.

문제해결

아래 코드는 조합을 사용해서 나올 수 있는 팀의 능력치를 구한 값을 power_start에 저장하는 코드이다.

이렇게 저장된 power_start는 가능한 팀의 모든 경우의 능력치를 가지고 있다.

for i in itertools.combinations(range(N),N//2):
    power_team = 0
    for j in itertools.combinations(i,2):
        # 각각의 팀의 능력치의 합
        power_team += power[j[0]][j[1]] + power[j[1]][j[0]]
    power_start.append(power_team)

따라서 이 power_start의 가운데를 슬라이싱하여 2개의 팀으로 나누어야 한다.
슬라이싱하여 power_start와 power_link로 나누었을 때, power_start[0] 팀과 power_link[-1] 팀이 서로 적대하게 되는 것이다.

power_link = power_start[len(power_start)//2:]
power_start = power_start[:len(power_start)//2]

이제 능력치의 차이의 최솟값을 저장하는 코드를 구현해야 한다.
능력치의 차이는 abs()를 사용하여 절대값으로 계산했다.

min_power = float("inf")
# 능력치의 합끼리 뺐을 때 가장 작은 차이를 보이는 것을 return
for i in range(len(power_link)):
    min_power = min(min_power, abs(power_start[i] - power_link[len(power_link)-1-i]))
print(min_power)

제출코드

import sys
import itertools
N = int(sys.stdin.readline())
power = []
for i in range(N):
    power.append(list(map(int,sys.stdin.readline().split())))
power_start = []
team = []
# 조합인거지 NCN/2
# N/2로 나눠서 나올 수 있는 팀의 리스트는 i/i를 기준으로 나눴을 때 나오는 값들이다~ 따라서 조합을 사용한다.
for i in itertools.combinations(range(N),N//2):
    power_team = 0
    for j in itertools.combinations(i,2):
        # 각각의 팀의 능력치의 합
        power_team += power[j[0]][j[1]] + power[j[1]][j[0]]
    power_start.append(power_team)
power_link = power_start[len(power_start)//2:]
power_start = power_start[:len(power_start)//2]
min_power = float("inf")
# 능력치의 합끼리 뺐을 때 가장 작은 차이를 보이는 것을 return
for i in range(len(power_link)):
    min_power = min(min_power, abs(power_start[i] - power_link[len(power_link)-1-i]))
print(min_power)