[python_파이썬_Pass]백준_14889번_스타트와 링크_백트레킹_풀이

공부하는허딩크 : https://www.youtube.com/live/L_d3lgvqAlM?feature=shared

역시 실버1부터는 문제를 이해하기도 벅차네...

 

<첫번째 시도 : 실패_N = 4일때만 가능한 코드임>

import sys

import itertools

input = sys.stdin.readline

"""아래의 코드는 N = 4일때 가능함 그 이상되면 불가능"""

#1. 초기화 및 입력

N = int(input())

S = []

players = [i for i in itertools.combinations(range(1, N + 1), N // 2)]

skill = []

for _ in range(N):

    temp = list(map(int, input().split()))

    S.append(temp)

#모든 능력치 skill에 종합    

for player in players:

    i, j = player

    skill.append(S[i-1][j-1] + S[j-1][i-1])

#skill의 차이 구하기

gaps = [i for i in itertools.combinations(skill, 2)]

answer = []

for gap in gaps:

    i, j = gap

    answer.append(abs(i - j))

   

print(min(answer))

 

<두번째 시도 : 일단 1시간 10분 걸렸음... 채점 중이 늦게 올라가네...."맞았습니다.!!">

 

와... 힘들었다..... 일단 백트레킹이 아닌 itertools로 풀어보려고 고민했는데 처음에 쉽게 풀 수 있을거라고 생각했는데

조금씩 깊게 들어가다보니 이것저것 조건을 확인해야 했다.

이게 되는 것도 신기함...

일단, 2명이든 3명이든 조합을 뽑아내서 그 조합의 반대의 조합도 같이 뽑아냈다.

이게 딱 봐도 비효율 적인데, N = 6일때 (0, 1, 2)플레이어가 팀을 이루면 반대되는 (3, 4, 5)의 플레이어가 있기 때문에

그걸 뽑아줘서 a_skill점수를 더하고 b_skill점수를 더해서 이 둘의 차이를 abs()로 절대값으로 skills리스트에 넣어준다.

근데 나중에 (3, 4, 5)의 팀이 나왔을때 또 (0, 1, 2)의 팀과 비교하게 됨으로 비효율 적이어서 통과가 안될 줄 알았다. 

import sys

import itertools

input = sys.stdin.readline

#1. 초기화 및 입력

N = int(input())

S = []

players = [i for i in itertools.combinations(range(N), N // 2)]

skills = []

for _ in range(N):

    temp = list(map(int, input().split()))

    S.append(temp)

#인원수 고려 : players의 조합들을 꺼내서 2명의 조합으로 변경 후 능력치 뽑아내기

for i in players:

    #첫번째 조합의 player 조합 뽑기

    player = [j for j in itertools.combinations(i, 2)]

    a_skill = []

    for k in player:

        a, b = k

        a_skill.append(S[a][b] + S[b][a])

 

    #첫번째 조합 player의 반대 조합 뽑기

    r_players = []

    for r_i in range(N):

        if r_i not in i:

            r_players.append(r_i)

   

    r_player = [o for o in itertools.combinations(r_players, 2)]

    b_skill = []

    for j in r_player:

        c, d = j

        b_skill.append(S[c][d] + S[d][c])

   

    skills.append(abs(sum(a_skill) - sum(b_skill)))

print(min(skills))

 

<스터디원 풀이 참고>

와.... 어떤 변수가 필요하고 어떻게 함수를 그려나가야 하는지 아직 잘 모르겠다.

이걸 20분만에 해결하는 스터디원들이 정말 부럽다....

import sys

input = sys.stdin.readline

N = int(input())

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

"""팀을 만드는 함수와 skill점수 check하는 함수 2가지 필요"""

team = [0 for _ in range(N)]

gap = []

def make_team(cnt, start):

    if cnt == N // 2:

        d = gaps()

        gap.append(d)

        return

   

    for i in range(start, N):

        team[i] = 1

        make_team(cnt + 1, i + 1)

        team[i] = 0

   

def gaps():

    A_team = 0

    B_team = 0

    for i in range(N):

        for j in range(i + 1, N):

            if team[i] and team[j]:

                A_team += S[i][j] + S[j][i]

            elif not team[i] and not team[j]:

                B_team += S[i][j] + S[j][i]

    return abs(A_team - B_team)

make_team(0, 0)

print(min(gap))