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

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

백트래킹 문제 너무 어렵다..

사실 백트래킹 문제인데 계속 브루트포스로 풀게된다.

 

왜 이렇게 구현아이디어가 부족하지..

 

이번에도 일단 브루트포스로 모든 쌍의 값을 구한다음에

차이를 하나씩 구하면서 차이가 만약에 0인경우 바로 출력될 수 있도록 구현했다.

나름 0인 경우에 바로 출력되고 for문을 탈출하니까 나름(??) 백트래킹이 아닐까.. 

 

def making_speclist(arr):
    for i in range(len(arr)):
        tempsum=0
        temp=list(permutations(arr[i],2))
        for j in temp:
            tempsum+=slist[j[0]-1][j[1]-1]
        arr[i]=tempsum
    return arr
    
import sys
from itertools import permutations, combinations
input=sys.stdin.readline
N=int(input())
slist=[list(map(int,input().split())) for _ in range(N)]
teamlist=list(combinations([i+1 for i in range(N)],N//2)) #팀으로 만들 수 있는 멤버 조합
speclist=making_speclist(teamlist) #팀의 시너지스펙 리스트
diff=100
for i in range(len(speclist)//2):
    if speclist[i]==speclist[len(speclist)-(i+1)]:
        diff=0
        break
    diff=min(diff,abs(speclist[i]-speclist[len(speclist)-(i+1)]))

print(diff)

일단 팀으로 만들 수 있는 멤버 조합을 구하고,

그 멤버 조합의 시너지를 구하는데 필요한 i,j 쌍을 순열로 만들었다.

(1,2)와(2,1)이 다른 값이라 순열로 만들었음.

처음에는 순열을 모두 구해서 돌리려고 했는데

어차피 시너지값은 그 칸에 맞는 값끼리 더하면 되는거라고 생각해서

임시로 templist를 만들어서 시너지값을 다 더한다음에 return 시켰다.

 

노트에 써서 하다보니 멤버 조합리스트가 양극단에서 중앙방향으로 서로 쌍을 이루는 것이었다!

예를들면 (1,2) & (3,4) 와 같이 스타트팀과 링크팀의 쌍이 생기는것.

 

그래서 차이를 계산할 때 양 극단에서 중앙으로 차례로 빼다가

최솟값 0이되는 경우 for문을 바로 탈출

아닌 경우에는 최솟값을 계속 찾는 원리로 코딩을 했다.

 

그래도 시간이 892ms가 나오던데,

다른 분 코딩을 보니까 100ms 초반대가 나와서 봤는데

훨씬 짧고 간결한 코딩이었다.

 

하지만 아무리 생각해봐도 코딩의 원리를 이해 못하겠어서 

나의 풀이로 take 할 수가 없었다 ㅜㅜ..

 

앞으로 계속 하다보면 더 나아지겠지!