백준 14889 스타트와 링크 파이썬

백준 14889 스타트와 링크 풀이

접근방식

1. 참가 인원의 능력치 리스트를 입력받기
2. combinations 모듈을 활용하여 2팀으로 나누는 조합 구하기
3. 조합에 맞춰서 각 팀의 모든 능력치 합계 더하기
4. 스타트팀과 링크팀의 능력치 합계 차를 구하기
5. abs함수를 활용하여 절댓값으로 비교하고 min 함수로 갱신하기

# 입력받기
import sys
from itertools import combinations as c

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

# 능력치 테이블 입력받기
team = [list(map(int, input().split())) for _ in range(n)]

# 최솟값으로 갱신하기 위해 무한대값을 초기값으로 설정해준다.
MIN = int(1e9)

# 인원에 관계없이 2팀으로 나누도록 조합을 구한다.
combis = c(range(n), n//2)

# 조합에 접근
for combi in combis:
    a = set(combi)
    # 스타트팀을 a라고 가정했을 때
    # b는 a를 제외한 나머지 인원으로 할당
    b = list(set(range(n)) - a)
    # set을 리스트 타입으로 변환
    a = list(a)
    # 초기 능력치 합계 할당
    start, link = 0, 0
    for i in range(n//2-1):
        for j in range(i+1, n//2):
            start += team[a[i]][a[j]] + team[a[j]][a[i]]
            link += team[b[i]][b[j]] + team[b[j]][b[i]]
    MIN = min(MIN, abs(start-link))

print(MIN)

보충 설명

    # 초기 능력치 합계 할당
    start, link = 0, 0
    for i in range(n//2-1):
        for j in range(i+1, n//2):
            start += team[a[i]][a[j]] + team[a[j]][a[i]]
            link += team[b[i]][b[j]] + team[b[j]][b[i]]
    MIN = min(MIN, abs(start-link))

print(MIN)

리스트가 0부터 시작한다는 것을 고려합니다

• n = 6일 경우, [0, 1, 2], [3, 4, 5] 등의 두 팀으로 나눌 수 있습니다.
• 인덱싱 순서는 크게, [i][j] -> a[i]a[j] -> team[a[i]][a[j]]의 순서로 접근하게 됩니다.
• 이때, a = [0,1,2]인 경우 [0][1], [0][2], [1][0], [1][2], [2][0], [2][1]의 값을 더해야 합니다.
• 6가지 경우를 비슷한 것끼리 묶어보면 다음과 같습니다.
• ([0][1], [1][0]), ([0][2], [2][0]), ([1][2], [2][1])
• i = 0일 경우, j = 1, 2
• i = 1일 경우, j = 2 를 가지므로 이중 for문에서 range를 위의 코드와 같이 설정하면
• 모든 경우에 대한 능력치에 접근할 수 있습니다.

해당 문제는 실버2레벨에 해당했고, dfs형태로도 푼 코드들이 많이 있습니다.

combinations 모듈을 사용하지 않은 코드도 있고, 다양한 접근법이 있으므로

여러 코드를 참고하는 것이 좋은 것 같습니다.

이 문제에서 까다로웠던 부분은 어떠한 인덱스로 접근해서 합계를 구할 것인지와

스타트팀에 속하지 않은 인원을 어떻게 링크팀으로 인식하게 할 것인가라고 생각합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady