[백준] 14889 - 스타트와 링크 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 14889번: 스타트와 링크

1. 문제

1. N명의 사람을 2/N명으로 이루어진 2개의 팀으로 나눈다.
2. 능력치 S_ij와 S_ji 는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다.
3. 두 팀의 총능력치 차이가 최소일 때 능력치 차이를 출력한다.

2. 풀이

브루트포스를 이용한 문제 풀이

1. True 와 False 2개의 팀으로 나눈다.
2. 브루트포스를 통해 모든 선수가 True 팀일 경우와 False팀일 때를 구한다.
3. True 팀이 2/N 이 되면 두 팀의 능력치 차이를 출력한다.

3. 코드

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
T = [False] * N
mn = float('inf')

def solution():
    global mn

    def team(cnt, idx):
        global T, mn
        if idx == N:
            return
        if cnt == N//2: # True 팀이 2/N이면 능력치 계산
            val = 0
            for i in range(N):
                for j in range(i+1, N): # range(N) -> range(i+1, N) 을 통해 반복횟수를 줄인다
                    if T[i] and T[j]: # 반복횟수를 줄이기 위해 두 선수의 능력치 한번에 계산
                        val += S[i][j] 
                        val += S[j][i] 
                    if not T[i] and not T[j]:
                        val -= S[i][j]
                        val -= S[j][i]
            mn = min(mn, abs(val))
            return

        T[idx] = True # 이 선수가 True 팀일 경우
        team(cnt+1, idx+1) # cnt 는 True 팀의 인원
        T[idx] = False # 이 선수가 False 팀일 경우
        team(cnt, idx+1)

    team(0, 0)
    return mn

print(solution())

• 결과는 3288 ms 나왔다.

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋