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

풀이 및 해설(주석) - v1

import sys
from itertools import combinations

N = int(sys.stdin.readline())
skills = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]

nst = [i for i in range(1, N+1)]

rst = 9e9
# 조합 사용해서 풀기 N은 짝수이므로 일단 두 팀이 될 수 있는 모든 조합을 생성
candi_t1_all = list(combinations(nst, N//2))

# t1의 팀이 정해지면 t2는 그 외의 나머지 선수니까 구한 조합의 반만 사용해도 됨
for i in range(len(candi_t1_all)//2):
    t1 = candi_t1_all[i]
    t2 = [i for i in range(1, N+1) if i not in t1]
    tmp = 0
    t1_score = 0
    t2_score = 0

    # t1의 모든 스킬 더해주기
    for t1_man in t1:
        for t1_ano in t1:
            t1_score += skills[t1_man-1][t1_ano-1]

    # t2의 모든 스킬 더해주기
    for t2_man in t2:
        for t2_ano in t2:
            t2_score += skills[t2_man-1][t2_ano-1]

    # 두 팀의 능력치의 차이
    tmp = abs(t1_score - t2_score)
    rst = min(rst, tmp)

print(rst)

 

---

후기

• 백트래킹 문제라는데 나는 조합을 사용하여 구했다. (알고 보니 조합을 백트래킹으로 만드는 거..)
• 두 팀으로 나누는 경우이기 때문에 조합밖에 생각이 안났다.
• 일단 통과는 했는데, tmp를 구하는 과정을 두 팀의 능력치 더하는걸 한번에 해버리고 tmp가 rst보다 커지면,
• break를 걸어주어 가지를 칠 수는 있겠지만, 통과했으니 그냥 안하겠다.

 

풀이 - v2

import sys

def solve(n, index, N, skill, visit, a_skill, b_skill, rst):
    if n == N//2:
        a_team = 0
        b_team = 0
        for i in range(N):
            if visit[i]:
                a_team += a_skill[i]
            else:
                b_team += b_skill[i]

        return min(abs(a_team - b_team), rst)

    for i in range(index, N):
        visit[i] = True
        rst = min(solve(n+1, i+1, N, skill, visit, a_skill, b_skill, rst), rst)
        visit[i] = False

    return rst

def main():
    N = int(sys.stdin.readline().strip())
    skill = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]

    visit = [0] * N

    a_skill = [sum(r) for r in skill]
    b_skill = [sum(c) for c in zip(*skill)]

    print(solve(0, 0, N, skill, visit, a_skill, b_skill, 9e9))


if __name__ == '__main__':
    main()