알고리즘/백준

링크와 스타트 15661번 백준

글을 쓰는 개발자 2020. 12. 8. 21:55
반응형

문제:www.acmicpc.net/problem/15661

 

15661번: 링크와 스타트

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100

www.acmicpc.net

 

 
import sys
N=int(sys.stdin.readline())
ar=[]
passing=[False]*(N)
for _ in range(N):
    ar.append(list(map(int,sys.stdin.readline().split())))
li = [int(i) for i in range(N)]
ret=10e9
def func(ans,celi,aim):
    global li
    global passing
    global ret
    if celi==aim:
        return
    for i in range(1,len(li)):
        if not passing[i] and ans[-1]<li[i]:
            passing[i]=True
            ans.append(i)
            val1=0
            val2=0
            link = set(li)
            link=link.difference(set(ans))
            for x in ans:
                for y in ans:
                    if x!=y:
                        val1+=ar[x][y]
            for a in link:
                for b in link:
                    if a!=b:
                        val2+=ar[a][b]
            ret=min(ret,abs(val1-val2))
            func(ans,celi+1,aim)
            ans.pop()
            passing[i]=False
ans=[0]
passing[0]=True
func(ans,0,N)
print(ret)

위 문제는 스타트와 링크와 상당히 유사한 문제이지만 다른 점이 있다면 인원 구성이 달라질 수 있다는 것이 크다

그래서 for문 돌 때마다 두 그룹의 능력치를 비교하는 코드를 짰다. (하지만 python3에서는 시간초과가 나서 pypy3로 제출하였다.)

 

반응형