[BOJ/백준] 14889. 스타트와링크 (Python)
https://www.acmicpc.net/problem/14889
Problem
N명의 사람들을 N//2명으로 나누어 각 시너지의 합들을 더한 조합의 최솟값을 찾는 문제
Solution
1)combination을 통해 그룹 나누기
2)permutation을 통해 나눈 그룹의 조합들을 구해주기
3)나눈 그룹들의 시너지 합을 표에서 찾아 더해주기
4)최솟값을 구하기
Python Code
import sys
from itertools import combinations
from itertools import permutations
N=int(sys.stdin.readline())
NList=[i for i in range(1,N+1)]
arrList=[]
for _ in range(N):
tmp=list(map(int,sys.stdin.readline().split()))
arrList.append(tmp)
combiList=list(combinations(NList,N//2))
Asum=0
Bsum=0
minValue=1e9
def sumFunction(setRawPermu,setRemainPermu):
global Asum
global Bsum
global minValue
Asum=0
Bsum=0
for row in setRawPermu:
Asum+=arrList[row[0]-1][row[1]-1]
for row in setRemainPermu:
Bsum+=arrList[row[0]-1][row[1]-1]
minValue=min(minValue,abs(Asum-Bsum))
for combi in combiList:
setRaw=list(combi)
setRemain=list(set(NList)-set(setRaw))
setRawPermu=list(permutations(setRaw,2))
setRemainPermu=list(permutations(setRemain,2))
sumFunction(setRawPermu,setRemainPermu)
print(minValue)
Author And Source
이 문제에 관하여([BOJ/백준] 14889. 스타트와링크 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@iwsl1234/BOJ백준-14889.-스타트와링크-Python
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
from itertools import combinations
from itertools import permutations
N=int(sys.stdin.readline())
NList=[i for i in range(1,N+1)]
arrList=[]
for _ in range(N):
tmp=list(map(int,sys.stdin.readline().split()))
arrList.append(tmp)
combiList=list(combinations(NList,N//2))
Asum=0
Bsum=0
minValue=1e9
def sumFunction(setRawPermu,setRemainPermu):
global Asum
global Bsum
global minValue
Asum=0
Bsum=0
for row in setRawPermu:
Asum+=arrList[row[0]-1][row[1]-1]
for row in setRemainPermu:
Bsum+=arrList[row[0]-1][row[1]-1]
minValue=min(minValue,abs(Asum-Bsum))
for combi in combiList:
setRaw=list(combi)
setRemain=list(set(NList)-set(setRaw))
setRawPermu=list(permutations(setRaw,2))
setRemainPermu=list(permutations(setRemain,2))
sumFunction(setRawPermu,setRemainPermu)
print(minValue)
Author And Source
이 문제에 관하여([BOJ/백준] 14889. 스타트와링크 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@iwsl1234/BOJ백준-14889.-스타트와링크-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)