백준 14889 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

처음 풀어보는 삼성 sw 역량 기출문제!

중간에 이것저것 테스트 파일 만들어서 확인해본다고 약 1시간 정도 소요 됐던거 같다

문제를 해결하기 위한 키워드는 크게 2가지로 볼수 있다

 

📌 해결순서

1. 팀 나누기

팀을 어떻게 나눌까 생각하다가 백준에 있는 백트래킹 기초 문제중에 n과 m 시리즈가 있다

1 부터 n 까지의 자연수중에 중복없이 m개의 수를 고르는 문제인데 이걸 사용해서 풀었다

문제에서는 번호를 1 부터 N 까지 배정했지만 2차원 배열의 인덱스를 좀더 쉽게 사용하기 위해서 0 부터 N - 1 까지 번호를 부여했다.

오름차순으로만 만들어서 출력하면

[0,1] vs [2,3] 

[0,2] vs [1,3]

[0,3] vs [2,3]

3번의 비교를 해야함을 알수 있다.

 

2. 능력치 합산 비교하기

 

총 인원이 4명이고 각 팀에 2명씩 밖에 없는 경우에는 따로 계산 해줬다. 그러지 않으면 index 초과 에러가 발생한다

번호가 [0, 1, 2] 인 사람들이 한팀이 되었을때 이 팀의 총 능력치를 구하려면

01 + 10 + 02 + 20 + 12 + 21 을 모두 더해야한다

여기서 01, 02, 12 만 구하면 되므로 이중반복문으로 인덱스를 뽑았다

for i in range(len(team) - 1):
            for j in range(i + 1, len(team)):
                sum += lst[team[i]][team[j]]
                sum += lst[team[j]][team[i]]

두 팀의 능력 합이 구해지면 차를 구하고 최솟값을 구하면 해결할 수 있다!

 

📌코드

import sys


def make_team(start):
    if len(tmp) == n // 2:
        team.append(list(tmp))
        return

    for i in range(start, n):
        tmp.append(i)
        make_team(i + 1)
        tmp.pop()


def ability(team, sum):
    if len(team) == 2:
        sum += lst[team[0]][team[1]]
        sum += lst[team[1]][team[0]]
    else:
        for i in range(len(team) - 1):
            for j in range(i + 1, len(team)):
                sum += lst[team[i]][team[j]]
                sum += lst[team[j]][team[i]]

    return sum


n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]

ans = sys.maxsize
tmp = []
team = []

make_team(0)

for i in range(len(team) // 2):
    ans = min(ans, abs(ability(team[i], 0) - ability(team[-1-i], 0)))

print(ans)