[Python]14889. 스타트와 링크

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

14889번: 스타트와 링크

---

 

이 문제는 0*n//2 와 1*n//2 로 이루어진 n 길이의 순열을 만들어서 이중포문에 넣으면 되는 간단한 문제이다.

 

def next_perm(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True
 
def cal_score(a, start, link):
    start_score = link_score = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if a[i] == start:
                if a[i] == a[j]:
                    start_score += stat[i][j]
            elif a[i] == link:
                if a[i] == a[j]:
                    link_score += stat[i][j]
    return start_score, link_score
 
n = int(input())
stat = [list(map(int, input().split())) for _ in range(n)]
lst = [0]*(n//2)+[1]*(n//2)
answer = 9876543210
 
while True:
    team_start, team_link = cal_score(lst, 0, 1)
    answer = min(abs(team_start-team_link), answer)
    if not next_perm(lst):
        break
 
print(answer)