[백준 14889] 스타트와 링크 (Python)

 

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

문제풀이

N, board : 입력값

check : 두 개의 팀을 나누기 위한 bool 순열

tmp : 순열의 마지막까지 도달했는지 확인하기 위한 check의 마지막 순열

ans : 결과값(두 팀의 능력치 차이의 최솟값)

 

next_permutation(a) : 특정 순열의 다음 순열을 구하는 함수

 

 

단순히 bool 순열을 구하기만 하면 풀 수 있는 문제이다. python itertools의 permutation을 쓰면 시간이 좀 더 빠르게 나오지 않을까(?) 라고 예상해본다.

 

 

1. check 리스트의 절반은 True, 나머지는 False로 설정함으로써 두 개의 팀으로 나눈다.

이때 순열의 마지막에 도달했는지 확인하기 위해 tmp를 순열의 마지막으로 선언한다.

 

2. 순열을 정렬해줌으로서 순열의 첫번째로 변경한다.

 

3. False 팀과 True팀으로 나누어서 check리스트에서 각각의 값에 해당하는 인덱스를 넣어준다.

 

4. 팀별로 점수를 더해본다.

ex ) true_list : [1,3,5]  false_list : [0, 2, 4]

t1 = board[1][3] + board[3][1] + board[1][5] + board[5][1] + board[3][5] + board[5][3]

t2 = board[0][2] + board[2][0] + board[0][4] + board[4][0] + board[2][4] + board[4][2]

 

5. t1과 t2의 차이와 ans 중 최소값을 ans에 저장한다.

 

6. 3-5 과정을 순열의 마지막에 도달할 때 까지 반복한다.

 

 

코드

import sys

def next_permutation(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]
        j -= 1
        i += 1
    return True

if __name__ == '__main__':
    N = int(input())
    board = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
    check = [False] * N
    # N 은 짝수이므로 두개의 팀인 N // 2로 나눔
    for i in range(N // 2):
        check[i] = True
    # 순열의 끝까지 왔는지 확인하기 위한 tmp
    tmp = [x for x in check]
    # 정렬 함으로써 순열의 시작
    check.sort()
    ans = sys.maxsize

    while True:
        t1, t2 = 0, 0
        # False 팀과 True 팀
        false_list, true_list = [], []
        # 팀 나누기
        for i in range(N):
            if check[i]: true_list.append(i)
            else: false_list.append(i)
        # 팀 별로 점수 더해보기
        for i in range(N // 2 - 1):
            for j in range(i + 1, N // 2):
                t1 += board[true_list[i]][true_list[j]] + board[true_list[j]][true_list[i]]
                t2 += board[false_list[i]][false_list[j]] + board[false_list[j]][false_list[i]]
        ans = min(ans, abs(t1 - t2))
        # 순열의 끝이면 종료
        if tmp == check:
            break
        # 다음 순열 호출
        next_permutation(check)
    print(ans)

 

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!